Leaf-to-leaf paths of many lengths

2025/01/30 by Francesco Di Braccio, Di Braccio, Francesco, Kyriakos Katsamaktsis +3 · 1 citation
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Slime Mold and Myxomycetes Research

paper · pdf · doi:10.48550/arxiv.2501.18540

openalex publication_date 2025/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that every tree of maximum degree Δ with ℓ leaves contains paths between leaves of at least log_Δ-1((Δ-2)ℓ) distinct lengths. This settles in a strong form a conjecture of Narins, Pokrovskiy and Szabó. We also make progress towards another conjecture of the same authors, by proving that every tree with no vertex of degree 2 and diameter at least N contains N^2/3/6 distinct leaf-to-leaf path lengths between 0 and N.

Cited by

• Leaf to leaf path lengths in trees of given degree sequence

Related

• Leaf to leaf path lengths in trees of given degree sequence
• Leaf-to-leaf paths and cycles in degree-critical graphs
• Bipartite Turán number of paths and other trees
• 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
• Spanning directed trees with many leaves