# Squared Distance Matrix of a Tree

December 9, 2014

## Speaker

Ravindra B. Bapat

## Affiliation

Indian Statistical Institute, Delhi

## Overview

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)2n-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 qd(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 Δ.