The Buratti–Horak–Rosa Conjecture for the Support Set {1, 2, x}

Abstract

Let Kv be the complete graph on the vertex set {0, 1, . . . , v − 1} with edge length ℓ(u, w) = min(|u − w| , v − |u − w|). A multiset L of v − 1 positive integers not exceeding ⌊v/2⌋ is realizable if some Hamiltonian path of Kv has L as its multiset of edge lengths. The Buratti– Horak–Rosa (BHR) Conjecture states that L is realizable if and only if for every divisor d of v the number of multiples of d in L is at most v − d; for prime v the condition is vacuous, and this is Buratti’s original conjecture. We consider the support set {1, 2, x} with x odd. Agirseven and Ollis (2024) proved that for this support the conjecture holds for all sufficiently large v except possibly when L = {1 a , 2 b , xc} with x odd and a < 3. We settle both exceptional cases a = 1 and a = 2 by explicit constructions. For every odd v and every odd x with 2x ≤ ⌊v/2⌋ we construct a Hamiltonian path of Kv realizing L1 = {1, 2 v−3 , x} and one realizing L2 = {1, 1, 2 v−4 , x}. Both are given as signed integer walks whose partial sums are pairwise distinct modulo v. The proof rests on the observation that these partial sums form three arithmetic progressions of common difference 2 — two consisting of even residues and one of odd residues — that together exhaust {0, 1, . . . , v − 1}; the decisive feature is that the last progression wraps around modulo v and completes precisely the residues left uncovered by the others. Combined with the known results for a ≥ 3 and the computational verification for v ≤ 37, this yields the BHR Conjecture for the whole support {1, 2, x} with x odd. Every structural lemma used in the argument is additionally checked by machine assertions over 143,850 parameter instances, with no failures. The verification scripts are included.

Keywords