Grid-based graphs, linear realizations, and the Buratti-Horak-Rosa conjecture

Label the vertices of the complete graph Kv with the integers {0, 1, …, v − 1} and define the length l of the edge between distinct vertices labeled x and y by l(x, y) = min (|y − x|,v − |y − x|). A realization of a multiset L of size v − 1 is a Hamiltonian path through Kv whose edge labels are L. The Buratti-Horak-Rosa (BHR) Conjecture is that there is a realization for a multiset L if and only if for any divisor d of v the number of multiples of d in L is at most v − d. We introduce “grid-based graphs" as a useful tool for constructing particular types of realizations, called “linear realizations,"especially when the multiset in question has a support of size 3. This lets us prove many new instances of the BHR Conjecture, including those for multisets of the form {1a, xb, yc} when a ≥ x + y − ϵ, where ϵ is the number of even elements in {x, y}, and those for all multisets of the following forms for sufficiently large v with gcd (v, y) = 1 for all y ∈ L: - {1a, 2b, xc}, except possibly when a ∈ {1, 2} and x is odd, - {1a, xb, (x + 1)c}. This establishes that there are infinitely many sets U of size 3 for which there are infinitely many values of v where the BHR Conjectureholds for each multiset with support U. We also show that the BHR Conjecture holds for {1a, xb, (x + 1)c} when x ∈ {7, 9, 10}and gcd (v, x) = gcd (v, x + 1) = 1.