Homogeneous linear recurrence relations of the determinants of distance matrices of trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915232391102464 |
|---|---|
| author | Liu, Zhiqi Zhou, Hui |
| author_facet | Liu, Zhiqi Zhou, Hui |
| contents | In 1971, by induction on $n$ and using a two-term linear recurrence relation, Graham and Pollak got a beautiful formula $$\det(D_n)=-(n-1)(-2)^{n-2}$$ on the determinant of distance matrix $D_n$ of a tree $T_n$ on $n$ vertices. The recurrence relations are very crucial when proving this formula by inductive method: in 2006, Yan and Yeh used two-term and three-term recurrence relations; in 2020, Du and Yeh used a homogeneous linear three-term recurrence relation. In this paper, we analyze the subtree structure of the tree and find four-term, five-term, six-term and seven-term homogeneous linear recurrence relations on $\det(D_n)$, as a corollary new proofs of Graham and Pollak's formula can be given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05337 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Homogeneous linear recurrence relations of the determinants of distance matrices of trees Liu, Zhiqi Zhou, Hui Combinatorics 05C05, 05C12, 15A15 In 1971, by induction on $n$ and using a two-term linear recurrence relation, Graham and Pollak got a beautiful formula $$\det(D_n)=-(n-1)(-2)^{n-2}$$ on the determinant of distance matrix $D_n$ of a tree $T_n$ on $n$ vertices. The recurrence relations are very crucial when proving this formula by inductive method: in 2006, Yan and Yeh used two-term and three-term recurrence relations; in 2020, Du and Yeh used a homogeneous linear three-term recurrence relation. In this paper, we analyze the subtree structure of the tree and find four-term, five-term, six-term and seven-term homogeneous linear recurrence relations on $\det(D_n)$, as a corollary new proofs of Graham and Pollak's formula can be given. |
| title | Homogeneous linear recurrence relations of the determinants of distance matrices of trees |
| topic | Combinatorics 05C05, 05C12, 15A15 |
| url | https://arxiv.org/abs/2504.05337 |