Principal minors of tree distance matrices

2024/11/18 by Richman, Harry, Farbod Shokrieh, Chenxi Wu +2
Mathematics · Physics and Astronomy · Computer Science · #Graph theory and applications #Complex Network Analysis Techniques #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2411.11488

Abstract

We prove that the principal minors of the distance matrix of a tree satisfy a combinatorial expression involving counts of rooted spanning forests of the underlying tree. This generalizes a result of Graham and Pollak, and refines a result of Graham and Lovász on the coefficients of the characteristic polynomial of the distance matrix. We also give such an expression for the case of trees with edge lengths. We use arguments motivated by potential theory on graphs. Our formulas can be expressed in terms of evaluations of Symanzik polynomials.

Related

• Principal minors of the distance matrix of a tree
• A Combinatorial Formula for Principal Minors of a Matrix with Tree-metric Exponents and Its Applications
• A Generalization of the Graham-Pollak Tree Theorem to Steiner Distance
• Non-intersecting paths and the determinant of the distance matrix of a tree
• A new result similar to the Graham-Pollak theorem