Document Type
Article
Abstract
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 𝑘 vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for 𝑘 =2 , this reduces to the ordinary definition of graphical distance. Here we show that the hyperdeterminant of the 𝑘 th order Steiner distance hypermatrix is always nonzero if 𝑘 is even, extending their result beyond 𝑘 =2 . Previously, the authors showed that the 𝑘 -Steiner distance hyperdeterminant is always zero for 𝑘 odd, so together this provides a generalization to all 𝑘 . We conjecture that not just the vanishing, but the value itself, of the 𝑘 -Steiner distance hyperdeterminant of an 𝑛 -vertex tree depends only on 𝑘 and 𝑛 .
Digital Object Identifier (DOI)
Publication Info
Published in Special Matrices, Volume 12, Issue 1, 2024.
APA Citation
Cooper, J. & Tauscheck, G. (2024). A generalization of the Graham-Pollak tree theorem to even-order Steiner distance. Special Matrices, 12(1), 20240018. https://doi.org/10.1515/spma-2024-0018
Rights
© 2024 the author(s), published by De Gruyter. This work is licensed under the Creative Commons Attribution 4.0 International License.