Leaf to leaf path lengths in trees of given degree sequence

Abstract

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 $\mathrm{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)\ge \mathrm{rad}(s)-{\log }_2\left(\mathrm{rad}(s)\right)$ for a tree $T$ with no vertex of degree $2$ and degree sequence $s$, and discuss possible improvements and variants.

6 pages, 0 figures