ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.