Note on the spectra of Steiner distance hypermatrices

Joshua Cooper¹ ; Zhibin Du²

¹University of South Carolina
²South China Normal University

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

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 \times \cdots \times 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 \geq 3$ and $k$ is odd, (b) $n=1$, or (c) $n=2$ and $k \equiv 1 \pmod{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^{k-1}-1$. Some related open questions are also discussed.

Détail

DOI : 10.37236/12850

Classification : 05C50, 05C12, 05C30
Mots-clés : distance spectral radius