Properties of the distance matrix of a tree
In a recent paper, Hakimi and Yau [1] have given the necessary and sufficient conditions for a matrix D to be the distance matrix of a linear graph. They also give a computational technique for determining a tree realization if it exists. The purpose of this note is to exhibit certain interesting algebraic properties of the distance matrix of a tree. Two algorithms for tree realization emerge from these properties. However, these algorithms are not elaborated on as there are many computational techniques which are faster than the original method proposed by Hakimi and Yau. Let G be a nonoriented weighted linear graph with n + 1 vertices and m edges, such that the weight assigned to edge i is a positive number . The length of any path from node i to node j is the sum of the weights of the edges in that path; the distance da between nodes i and j is the length of the shortest path from i to j, with dti taken as zero. The matrix whose elements are da is the distance matrix D. This development is limited to graphs which are trees [2], It is convenient to introduce the path matrix of a tree. If an arbitrary vertex r is taken as a reference vertex, then the path matrix P is defined as follows.