Narins–Pokrovskiy–Szabó conjecture on short leaf-to-leaf path lengths

From papers

A 1–3 tree is a tree in which every vertex has degree either 11 or 33. For a tree, a leaf-to-leaf path is a path whose endpoints are leaves. Narins–Pokrovskiy–Szabó conjecture. There exist a constant α>0\alpha>0 and a function N=N(n)N=N(n) with N(n)N(n)\to\infty as nn\to\infty such that every 1–3 tree of order nn contains at least αN\alpha N distinct leaf-to-leaf path lengths between 00 and NN. 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

No solutions have been posted yet.