Narins–Pokrovskiy–Szabó conjecture on short leaf-to-leaf path lengths
Narins–Pokrovskiy–Szabó conjecture on short leaf-to-leaf path lengths
A 1–3 tree is a tree in which every vertex has degree either or . For a tree, a leaf-to-leaf path is a path whose endpoints are leaves. Narins–Pokrovskiy–Szabó conjecture. There exist a constant and a function with as such that every 1–3 tree of order contains at least distinct leaf-to-leaf path lengths between and . The source gives upper and lower bounds with different exponents for this short-length problem, so the conjecture 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
Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian and Ziyuan Zhao, “Leaf-to-leaf paths and cycles in degree-critical graphs”, arXiv:2504.11656 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.