Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



Distance matrix of a graph and its realizability

Authors: S. L. Hakimi and S. S. Yau
Journal: Quart. Appl. Math. 22 (1965), 305-317
MSC: Primary 05.40
DOI: https://doi.org/10.1090/qam/184873
MathSciNet review: 184873
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The distances in a linear graph are described by a distance matrix $ D$. The realizability of a given $ D$ by a linear graph is discussed and conditions under which the realization of $ D$ is unique are established. The optimum realization of $ D$, (i.e., the realization of $ D$ with ``minimum total length"), is investigated. A procedure is given by which a tree realization of $ D$ can be found, if such a realization exists. Finally, it is shown that a tree realization, if it exists, is unique and is the optimum realization of $ D$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC: 05.40

Retrieve articles in all journals with MSC: 05.40

Additional Information

DOI: https://doi.org/10.1090/qam/184873
Article copyright: © Copyright 1965 American Mathematical Society

American Mathematical Society