2024/02/23 by Joshua Cooper, Cooper, Joshua, Gabrielle Tauscheck +1
Computer Science · Mathematics · #05C12 (Primary) 05C50 #15A69 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Mathematical Dynamics and Fractals #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2402.15621
openalex publication_date 2024/02/23 · openalex created_date 2024/02/28 · openalex updated_date 2026/07/28
Graham and Pollak showed in 1971 that the determinant of a tree's distance matrix depends only on its number of vertices, and, in particular, it is always nonzero. The Steiner distance of a collection of k vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for k=2, this reduces to the ordinary definition of graphical distance. Here, we show that the hyperdeterminant of the k-th order Steiner distance hypermatrix is always nonzero if k is even, extending their result beyond k=2. Previously, the authors showed that the k-Steiner distance hyperdeterminant is always zero for k odd, so together this provides a generalization to all k. We conjecture that not just the vanishing, but the value itself, of the k-Steiner distance hyperdeterminant of an n-vertex tree depends only on k and n.