Many short leaf-leaf path lengths in 1-3 trees

From papers

A 1-3 tree is a tree whose vertices have degrees 11 or 33, and a leaf-leaf path is a path with leaf endpoints. Many-short-paths conjecture. There is a constant α>0\alpha>0 and a function C(n)C(n) tending to infinity such that every 11-33 tree of order nn contains at least

αC(n)\alpha C(n)

distinct leaf-leaf path lengths between 00 and C(n)C(n). This refines the preceding path-count question by requiring a positive proportion of all lengths up to C(n)C(n). The paper's constructions rule out guaranteeing some sufficiently large individual path lengths, but leave open whether many short lengths must nevertheless occur.

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

Lothar Narins, Alexey Pokrovskiy and Tibor Szabó, “Graphs without proper subgraphs of minimum degree 3 and short cycles”, arXiv:1408.5289 (2014).

Solutions 0

No solutions have been posted yet.