Squared Distance Matrix of a Tree

Опубликовано 21 июня 2016, 23:16

Let G be a connected graph with vertex set V(G) = {1, …, n}. The distance between vertices i,j ∈ V(G), denoted d(i,j), is defined to be the minimum length (the number of edges) of a path from i to j. The distance matrix D(G), or simply D, is the n × n matrix with (i,j) -element equal to 0 if i = j and d(i,j) if i not = j. According to a well-known result due to Graham and Pollak, if T is a tree with n vertices, then the determinant of the distance matrix D of T is (-1) n-1 (n-1)2 n-2 . Thus the determinant depends only on the number of vertices in the tree and not on the tree itself. A formula for the inverse of the distance matrix of a tree was given by Graham and Lovász.Several generalizations of these two results have been proved. We first provide an overview of various distance matrices associated with a tree. These include a weighted analog of the classical distance matrix, a weighted analog with matrix weights, a q -analog, and the exponential distance matrix, which has the (i,j) -element equal to q d(i,j) . We then consider the entry-wise square of the distance matrix of a tree. Thus the squared distance matrix Δ has its (i,j) -element equal to d(i,j) 2 . In joint work with S. Sivasubramanian, we gave a formula for the determinant of Δ, which involves only the vertex degrees. It turns out that Δ is nonsingular if and only if the tree has at most one vertex of degree 2 and we give a formula for Δ -1 when it exists. When the tree has no vertex of degree 2, the formula for Δ -1 is particularly simple and depends on a certain “two-step" Laplacian of the tree. We also determine the inertia of Δ.