The distance matrix of a graph and its tree realization

Authors:
A. N. Patrinos and S. L. Hakimi

Journal:
Quart. Appl. Math. **30** (1972), 255-269

MSC:
Primary 05C05

DOI:
https://doi.org/10.1090/qam/414405

MathSciNet review:
414405

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The results of Hakimi and Yau and others in the realization of a distance matrix are generalized to graphs (digraphs) whose branches (arcs) may have negative weights. Conditions under which such matrices have a tree, hypertree or directed tree realization are given, uniqueness of these realizations is discussed and algorithms for their construction are indicated.

**[1]**R. W. Floyd,*Algorithm 97: shortest path*, Comm. ACM**5**, 345 (1962)**[2]**S. L. Hakimi and S. S. Yau,*Distance matrix of a graph and its realizability*, Quart. Appl. Math.**22**(1965), 305–317. MR**0184873**, https://doi.org/10.1090/S0033-569X-1965-0184873-7**[3]**A. J. Goldman,*Realizing the distance matrix of a graph*, J. Res. Nat. Bur. Standards Sect. B**70B**(1966), 153–154. MR**0200189****[4]**John David Murchland,*A fixed matrix method for all shortest distances in a directed graph and for the inverse problem*, Universität (TH) Fridericiana zu Karlsruhe, Karlsruhe, 1970. Zur Erlangung des akademischen Grades eines Doktors der Wirtschaftswissenschaften von der Fakultät für Geistes- und Sozialwissenschaften der Universität (TH) Fridericiana zu Karlsruhe genehmigte Dissertation. MR**0321787****[5]**K. A. Zareckiĭ,*Constructing a tree on the basis of a set of distances between the hanging vertices*, Uspehi Mat. Nauk**20**(1965), no. 6, 90–92 (Russian). MR**0199124****[6]**James Turner and William H. Kautz,*A survey of progress in graph theory in the Soviet Union*, SIAM Rev.**12**(1970), no. suppl., iv+68. MR**0268074**, https://doi.org/10.1137/1012125**[7]**J. M. S. Simões Pereira,*Some results on the tree realization of a distance matrix*, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 383–388 (English, with French summary). MR**0219441****[8]**F. T. Boesch,*Properties of the distance matrix of a tree*, Quart. Appl. Math.**26**(1968/1969), 607–609. MR**0265210**, https://doi.org/10.1090/S0033-569X-1969-0265210-7**[9]**B. P. Shay,*Some considerations of distances in a linear directed graph*, M. S. thesis, E. E. Dept., Northwestern University, Evanston, Ill., 1965**[10]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[11]**Claude Berge,*The theory of graphs*(English translation), Methuen, 1962**[12]**A. N. Patrinos,*The distance matrix of a graph and its tree realization*, M. S. thesis, E. E. Dept., Northwestern Univ., Evanston, Ill., 1971

Retrieve articles in *Quarterly of Applied Mathematics*
with MSC:
05C05

Retrieve articles in all journals with MSC: 05C05

Additional Information

DOI:
https://doi.org/10.1090/qam/414405

Article copyright:
© Copyright 1972
American Mathematical Society