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

From papers

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=n1\sum_{i=1}^d t_i=n-1

and, for every divisor qq of nn,

1id:qitinq,\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.

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

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.

Solutions 0

No solutions have been posted yet.