ON THE DISTANCE POLYNOMIAL OF A GRAPH

The distance matrix, which is a structure less common than the adjacency matrix [ l] , has been increasingly used in recent years in several different areas such as anthro pology [2], [3], graph theory [4] —[6], theory of communication [7], chemistry [ 8]- [ 1 0] , history [11], etc. The distance matrix (which is sometimes also called the metrics matrix) is, in a sense, a more complicated and also a richer structure than the adjacency matrix. While each (0, 1) symmetric matrix in which each diagonal entry is zero corresponds to a unique graph or digraph, this is not the case with the distance matrix (which is a symmetric matrix with diagonal entries zero, but not (0, 1)). We will consider finite connected graphs without loops. Graphs will be symbolized by G. The distance matrix D has the entries d n = 0 and dtj = the length of the shortest path between the vertices i and j. The distance polynomial of G is defined as det |x / — D | where / is the unit matrix