DISTANCE MATRIX POLYNOMIALS OF TREES

Let G be a finite connected graph. If x and y are vertices of G, one may define a distance function dG on G by letting dG(x, y) be the minimal length of any path between x and y in G (with dG(x, x) = 0). Thus, for example, dG(x, y) = 1 if and only if {x, y} is an edge of G. Furthermore, we define the distance matrix D(G) for G to be the square matrix with rows and columns indexed by the vertex set of G which has dG(x, y) as its (x, y) entry. In this paper we are concerned with properties of D(G) for the case in which G is a tree (i.e., G is acyclic). In particular, we precisely determine the coefficients of the characteristic polynomial of D(G). This determination is made by deriving surprisingly simple expressions for these coefficients as certain fixed linear combinations of the numbers of various subgraphs of G. © 1978.