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 . 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]**Edward F. Moore,*The shortest path through a maze*, Proc. Internat. Sympos. Switching Theory 1957, Part II, Harvard Univ. Press, Cambridge, Mass., 1959, pp. 285–292. MR**0114710****[2]**Joseph B. Kruskal Jr.,*On the shortest spanning subtree of a graph and the traveling salesman problem*, Proc. Amer. Math. Soc.**7**(1956), 48–50. MR**0078686**, https://doi.org/10.1090/S0002-9939-1956-0078686-7**[3]**R. C. Prim,*Shortest connection networks and some generalization*, Bell System Tech. Journal**36**(1957) 1389-1401**[4]**Richard Courant and Herbert Robbins,*What Is Mathematics?*, Oxford University Press, New York, 1941. MR**0005358****[5]**Sundaram Seshu and Myril B. Reed,*Linear graphs and electrical networks*, Addison-Wesley Series in the Engineering Sciences, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1961. MR**0147120****[6]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 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