Non-intersecting paths and the determinant of the distance matrix of a tree

2024/07/01 by Emmanuel Briand, Luis Esquivias-Quintero, Briand, Emmanuel +7
Computer Science · #05A15 (Secondary) #05C05 (Primary) 05A19 #Advanced Algebra and Logic #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2407.01227

openalex publication_date 2024/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present the first combinatorial proof of the Graham-Pollak Formula for the determinant of the distance matrix of a tree, via sign-reversing involutions and the Lindström-Gessel-Viennot Lemma. Our approach provides a cohesive and unified framework for the understanding of the existing generalizations and q-analogues of the Graham-Pollak Formula, and facilitates the derivation of a natural simultaneous generalizations for them.

Related

• A Generalization of the Graham-Pollak Tree Theorem to Steiner Distance
• Homogeneous linear recurrence relations of the determinants of distance matrices of trees
• A new result similar to the Graham-Pollak theorem
• A Generalization of the Graham-Pollak Tree Theorem to Even-Order Steiner Distance
• Principal minors of tree distance matrices