A generalization of the Graham-Pollak tree theorem to even-order Steiner distance

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

k = 2 k=2

, this reduces to the ordinary definition of graphical distance. Here we show that the hyperdeterminant of the

k k

th order Steiner distance hypermatrix is always nonzero if

k k

is even, extending their result beyond

k = 2 k=2

. Previously, the authors showed that the

k k

-Steiner distance hyperdeterminant is always zero for

k k

odd, so together this provides a generalization to all

k k

. We conjecture that not just the vanishing, but the value itself, of the

k k

-Steiner distance hyperdeterminant of an

n n

-vertex tree depends only on

k k

and

n n

.