2024/03/04 by Cooper, Joshua, Du, Zhibin
#05C12 (Primary) 05C50 #15A69 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2403.02287
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 \pmod6. 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 2k-1-1. Some related open questions are also discussed.