A Generalization of the Graham-Pollak Tree Theorem to Even-Order Steiner Distance
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914691943497728 |
|---|---|
| author | Cooper, Joshua Tauscheck, Gabrielle |
| author_facet | Cooper, Joshua Tauscheck, Gabrielle |
| contents | 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 $k$ vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for $k=2$, this reduces to the ordinary definition of graphical distance. Here, we show that the hyperdeterminant of the $k$-th order Steiner distance hypermatrix is always nonzero if $k$ is even, extending their result beyond $k=2$. Previously, the authors showed that the $k$-Steiner distance hyperdeterminant is always zero for $k$ odd, so together this provides a generalization to all $k$. We conjecture that not just the vanishing, but the value itself, of the $k$-Steiner distance hyperdeterminant of an $n$-vertex tree depends only on $k$ and $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15621 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Generalization of the Graham-Pollak Tree Theorem to Even-Order Steiner Distance Cooper, Joshua Tauscheck, Gabrielle Combinatorics 05C12 (Primary) 05C50, 15A69 (Secondary) G.2.2 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 $k$ vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for $k=2$, this reduces to the ordinary definition of graphical distance. Here, we show that the hyperdeterminant of the $k$-th order Steiner distance hypermatrix is always nonzero if $k$ is even, extending their result beyond $k=2$. Previously, the authors showed that the $k$-Steiner distance hyperdeterminant is always zero for $k$ odd, so together this provides a generalization to all $k$. We conjecture that not just the vanishing, but the value itself, of the $k$-Steiner distance hyperdeterminant of an $n$-vertex tree depends only on $k$ and $n$. |
| title | A Generalization of the Graham-Pollak Tree Theorem to Even-Order Steiner Distance |
| topic | Combinatorics 05C12 (Primary) 05C50, 15A69 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2402.15621 |