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 . The realizability of a given by a linear graph is discussed and conditions under which the realization of is unique are established. The optimum realization of , (i.e., the realization of with ``minimum total length"), is investigated. A procedure is given by which a tree realization of 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 .

**[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

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