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 Free Access

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?)

  • [1] E. F. Moore, Shortest path through a maze, Proc. Internatl. Symposium on Switching Circuits, Harvard University (1957) 285-292 MR 0114710
  • [2] J. B. Kruskal, Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7 (1960) 48-50 MR 0078686
  • [3] R. C. Prim, Shortest connection networks and some generalization, Bell System Tech. Journal 36 (1957) 1389-1401
  • [4] R. Courant and H. Robbins, What is mathematics, Oxford University Press, London, 1941 MR 0005358
  • [5] S. Seshu and M. B. Reed, Linear graphs and electrical networks, Addison-Wesley, Reading, Mass., 1961 MR 0147120
  • [6] O. Ore, Theory of graphs, Am. Math. Soc. Colloquium Publication 38 (1962) MR 0150753
  • [7] S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, J. Operations Res. 12 (1964) 450-459
  • [8] S. L. Hakimi and S. S. Yau, Distance matrix and the synthesis of N-port resistance networks, Network Theory Group, Tech. Report No. 5, Northwestern University, Evanston, Ill., 1963

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