On The Determinants And Inverses Of Distance Matrices Of Graphs

Let Tn be a tree on n vertices and D(Tn) its distance matrix. Graham and Pollak [8] showed that det(D(Tn))=(-l)n-12n-1), which only depends on the number of vertices of the tree, but has nothing to do with the structure. Various generalizations of Graham and Pollak’s formula can be found in [2,4,9]. A block of a graph is a maximal2-connected subgraph. This paper analyses the properties of determinant of distance matrix of a graph and calculates the de-terminants of distance matrices of the layer graph Layer(G, k)(see definition in section2.1), Hamming graphs H(q,n)(as a special case the hypercubes Qn), the joint graph GV H, the complete bipartite graph Km,n, graphs whose blocks are odd cycles and cliques, the cartesian product Pm x Pn and Pm x C2n. And then we get a generalization of Graham and Pollak’s formula. We get a generalization of Bapat’s theorem [4], and then give the formula of the inverse of distance matrix of a graph whose blocks are odd cycles and cliques. At last, we give some further problems and notes on the determinant, inverse and characteristic polynomial of the distance matrix of a graph.