Note on the spectra of Steiner distance hypermatrices
Abstract
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.
- Publication:
-
arXiv e-prints
- Pub Date:
- March 2024
- DOI:
- 10.48550/arXiv.2403.02287
- arXiv:
- arXiv:2403.02287
- Bibcode:
- 2024arXiv240302287C
- Keywords:
-
- Mathematics - Combinatorics;
- 05C12 (Primary) 05C50;
- 15A69 (Secondary);
- G.2.2
- E-Print:
- 6 pages, 0 figures