Leaf-to-leaf path length conjecture for trees with a given degree sequence
Leaf-to-leaf path length conjecture for trees with a given degree sequence
Let be a tree with degree sequence , and suppose that has no vertex of degree . Let denote the number of different lengths of leaf-to-leaf paths in , and let denote the minimum radius of a tree with degree sequence .
Leaf-to-leaf path length conjecture.
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 , 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
Sign in to submit a solution.
No solutions have been posted yet.