Buratti-Horak-Rosa conjecture on edge lengths of Hamiltonian paths
Let denote the vertices of a circulant instance, and let edge length refer to the corresponding circulant edge-length class, for . Let be nonnegative integers, where counts the edges of length .
Buratti-Horak-Rosa conjecture. If
and, for every divisor of ,
then there exists a Hamiltonian path on using exactly edges of length for each .
The conjecture characterizes the combinations of edge lengths that can occur in a Hamiltonian path and asserts that the divisibility inequalities are the only obstruction. Its prime-order case was conjectured by Buratti in the 2000s; the supplied text gives no evidence that the full conjecture has been resolved.
References
Primary source
Samuel C. Gutekunst, “Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds”, arXiv:2506.10758 (2025).
Additional references
4 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2402.08736, arXiv:2202.07733, arXiv:2105.00980.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.