Leaf to leaf path lengths in trees of given degree sequence

2025/07/14 by Rautenbach, Dieter, Scherer, Johannes, Werner, Florian
#05C05 #05C12 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.10351

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 \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)≥ \rm rad(s)-log₂(\rm rad(s)) for a tree T with no vertex of degree 2 and degree sequence s, and discuss possible improvements and variants.

Citations

• Leaf-to-leaf paths and cycles in degree-critical graphs
• Leaf-to-leaf paths of many lengths
• Graphs without proper subgraphs of minimum degree 3 and short cycles

Related

• Leaf-to-leaf paths of many lengths
• The existence of a spanning tree with leaf distance at least d and leaf degree at most k via the size or the spectral radius with respect to the minimum degree
• Leaf-to-leaf paths and cycles in degree-critical graphs
• On Minimum Terminal Distance Spectral Radius of Trees with Given Degree Sequence
• The median of the distance between two leaves in a phylogenetic tree