 |
Ravindra Bapat (LAMA Lecturer)  |
(Indian Statistical Institute, Delhi, INDIA) |
|
Title: Squared distance matrix of a tree |
Abstract: Let $G$ be a connected graph with vertex set $V(G) = \{1, \ldots, n\}.$
The distance between vertices $i,j \in V(G),$ denoted $d(i,j),$ is defined to
be the minimum length (the number of edges) of a path from $i$ to $j.$ ... more |
The distance matrix $D(G),$ or simply $D,$ is the $n \times 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\'asz.
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 $\Delta$ 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 $\Delta,$ which involves only the vertex degrees. It turns out that $\Delta$ is nonsingular if and only if the tree has at most one vertex of degree $2.$ Continuing the joint work, we obtain a formula for $\Delta^{-1},$ if it exists. When the tree has no vertex of degree $2,$ the formula for $\Delta^{-1}$ is particularly simple and depends on a certain ``two-step" Laplacian of the tree. |
|