Leaf to leaf path lengths in trees of given degree sequence
For a tree T , let l p ( T ) be the number of different lengths of leaf to leaf paths in T . For a degree sequence s of a tree, let 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 l p ( 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 l p ( T ) ≥ rad ( s ) − log 2 ( rad ( s ) ) for a tree T with no vertex of degree 2 and degree sequence s , and discuss possible improvements and variants.
Authors
- Johannes Scherer
- Dieter Rautenbach (ORCID: https://orcid.org/0000-0002-7214-042X)
- Florian Werner
Institutions
- Universität Ulm (DE)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2026-03-09
- DOI
- https://doi.org/10.1016/j.disc.2026.115086
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00