Distance Matrices of Trees: Invariants, Old and New

Abstract: In 1971, Graham and Pollak showed that if DT is the distance matrix of a tree T on n nodes, then det(DT) depends only on n, not T. This independence from the tree structure has been verified for many different variants of weighted bi-directed trees. In my talk:

1. I will present a general setting which strictly subsumes every known variant, and where we show that det(DT) - as well as another graph invariant, the cofactor-sum - depends only on the edge-data, not the tree-structure.

2. More generally - even in the original unweighted setting - we strengthen the state-of-the-art, by computing the minors of DT where one removes rows and columns indexed by equal-sized sets of pendant nodes. (In fact we go beyond pendant nodes.)

3. We explain why our result is the "most general possible", in that allowing greater freedom in the parameters leads to dependence on the tree-structure.

4. Our results hold over an arbitrary unital commutative ring. This uses Zariski density, which seems to be new in the field, yet is richly rewarding.

We then discuss related results for arbitrary strongly connected graphs, including a third, novel invariant. If time permits, a formula for D−1T will be presented for trees T, whose special case answers an open problem of Bapat-Lal-Pati (Linear Alg. Appl. 2006), and which extends to our general setting a result of Graham-Lovasz (Advances in Math. 1978). (Joint with Projesh Nath Choudhury).