Many short leaf-leaf path lengths in 1-3 trees
Many short leaf-leaf path lengths in 1-3 trees
A 1-3 tree is a tree whose vertices have degrees or , and a leaf-leaf path is a path with leaf endpoints. Many-short-paths conjecture. There is a constant and a function tending to infinity such that every - tree of order contains at least
distinct leaf-leaf path lengths between and . This refines the preceding path-count question by requiring a positive proportion of all lengths up to . 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
Sign in to submit a solution.
No solutions have been posted yet.