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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Leaf to leaf path lengths in trees of given degree sequence

Johannes Scherer, Dieter Rautenbach, Florian Werner
Discrete Mathematics
Computational Geometry and Mesh Generation
article

Leaf to leaf path lengths in trees of given degree sequence

Johannes Scherer, Dieter Rautenbach, Florian Werner
article en

Abstract

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.

Discrete MathematicsVol. 349(9)
Universität Ulm (DE)
Openalex Percentile: Top 30%
Computational Geometry and Mesh Generation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.