Note on the Spectra of Steiner Distance Hypermatrices

The Steiner distance of a set of vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices. The order-k Steiner distance hypermatrix of an n-vertex graph is the n × ⋯ × n (k terms) array indexed by vertices, whose entries are the Steiner distances of their corresponding indices. In the case of $k=2$, this reduces to the classical distance matrix of a graph. Graham and Pollak showed in 1971 that the determinant of the distance matrix of a tree only depends on its number n of vertices. Here, we show that the hyperdeterminant of the Steiner distance hypermatrix of a tree vanishes if and only if (a) n ≥ 3 and k is odd, (b) $n=1$, or (c) $n=2$ and k ≡ 1 6. Two proofs are presented of the $n=2$ case - the other situations were handled previously - and we use the argument further to show that the distance spectral radius for $n=2$ is equal to 2ᵏ⁻¹-1. Some related open questions are also discussed.