Leaf-to-leaf path length conjecture for trees with a given degree sequence

From papers

Let TT be a tree with degree sequence ss, and suppose that TT has no vertex of degree 22. Let lp(T)lp(T) denote the number of different lengths of leaf-to-leaf paths in TT, and let rad(s){\rm rad}(s) denote the minimum radius of a tree with degree sequence ss.

Leaf-to-leaf path length conjecture.

lp(T)rad(s)O(1).lp(T)\geq {\rm rad}(s)-O(1).

This conjecture seeks a lower bound on the number of distinct leaf-to-leaf path lengths determined by the degree sequence, strengthening bounds in terms of the number of leaves and maximum degree. The paper proves a weaker bound with a logarithmic error term, namely lp(T)rad(s)log2(rad(s))lp(T)\geq {\rm rad}(s)-\log_2({\rm rad}(s)), while the stated bounded-error improvement remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dieter Rautenbach, Johannes Scherer and Florian Werner, “Leaf to leaf path lengths in trees of given degree sequence”, arXiv:2507.10351 (2025).

Additional references

2 papers in this index state this conjecture (2014–2025). The statement above is taken from the most recent of them; the others are arXiv:1408.5289.

Solutions 0

No solutions have been posted yet.