A generalization of the Graham-Pollak tree theorem to even-order Steiner distance
Authors:
Open Access
- 1 January 2024
- journal article
- research article
- Published by Walter de Gruyter GmbH in Special Matrices
- Vol. 12 (1)
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 , 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 . 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 .
Keywords
This publication has 3 references indexed in Scilit:
- A generalization of the Graham-Pollak tree theorem to Steiner distanceDiscrete Mathematics, 2023
- Discriminants, Resultants, and Multidimensional Determinants1994
- On the Addressing Problem for Loop SwitchingBell System Technical Journal, 1971