Principal minors of the distance matrix of a tree

Abstract

Let $T=([n],E)$ be a tree and let $D=(d(i,j){)}_{i,j\le n}$ be the distance matrix of $T$. Let $S\subseteq [n]$. We give the first combinatorial proof for a formula to compute the principal minor of $D$ indexed by $S$, namely $\det D[S]$. This generalizes work of Graham and Pollak, as well as more recent works.

arXiv comment(26 pages) Original version, as presented at the British Combinatorial Conference 2024