Leaf to leaf path lengths in trees of given degree sequence
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915407295676416 |
|---|---|
| author | Rautenbach, Dieter Scherer, Johannes Werner, Florian |
| author_facet | Rautenbach, Dieter Scherer, Johannes Werner, Florian |
| contents | For a tree $T$, let $lp(T)$ be the number of different lengths of leaf to leaf paths in $T$. For a degree sequence $s$ of a tree, let ${\rm rad}(s)$ be the minimum radius of a tree with degree sequence $s$. Recently, Di Braccio, Katsamaktsis, Ma, Malekshahian, and Zhao provided a lower bound on $lp(T)$ in terms of the number of leaves and the maximum degree of $T$, answering a related question posed by Narins, Pokrovskiy, and Szabó. Here we show $lp(T)\geq {\rm rad}(s)-\log_2\left({\rm rad}(s)\right)$ for a tree $T$ with no vertex of degree $2$ and degree sequence $s$, and discuss possible improvements and variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10351 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Leaf to leaf path lengths in trees of given degree sequence Rautenbach, Dieter Scherer, Johannes Werner, Florian Combinatorics 05C05, 05C12 For a tree $T$, let $lp(T)$ be the number of different lengths of leaf to leaf paths in $T$. For a degree sequence $s$ of a tree, let ${\rm rad}(s)$ be the minimum radius of a tree with degree sequence $s$. Recently, Di Braccio, Katsamaktsis, Ma, Malekshahian, and Zhao provided a lower bound on $lp(T)$ in terms of the number of leaves and the maximum degree of $T$, answering a related question posed by Narins, Pokrovskiy, and Szabó. Here we show $lp(T)\geq {\rm rad}(s)-\log_2\left({\rm rad}(s)\right)$ for a tree $T$ with no vertex of degree $2$ and degree sequence $s$, and discuss possible improvements and variants. |
| title | Leaf to leaf path lengths in trees of given degree sequence |
| topic | Combinatorics 05C05, 05C12 |
| url | https://arxiv.org/abs/2507.10351 |