Buratti-Horak-Rosa conjecture on edge lengths of Hamiltonian paths

About 5 years old · traced to

Let [n]={1,2,…,n}[n]=\{1,2,\ldots,n\} denote the vertices of a circulant instance, and let edge length ii refer to the corresponding circulant edge-length class, for i=1,…,di=1,\ldots,d. Let t1,t2,…,tdt_1,t_2,\ldots,t_d be nonnegative integers, where tit_i counts the edges of length ii.

Buratti-Horak-Rosa conjecture. If

∑i=1dti=n−1\sum_{i=1}^d t_i=n-1

and, for every divisor qq of nn,

∑1≤i≤d: q∣iti≤n−q,\sum_{1\leq i\leq d:\,q\mid i}t_i\leq n-q,

then there exists a Hamiltonian path on [n][n] using exactly tit_i edges of length ii for each i=1,…,di=1,\ldots,d.

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

Never refreshed

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.