Grid-Based Graphs, Linear Realizations and the Buratti-Horak-Rosa Conjecture

Label the vertices of the complete graph Kᵥ with the integers \0, 1, …, v-1\ and define the { length} of the edge between distinct vertices labeled x and y by (x,y) = min( |y-x|, v - |y-x| ). A { realization} of a multiset L of size $v-1$ is a Hamiltonian path through Kᵥ 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 \1ᵃ, xᵇ, yᶜ \ 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 (v,y) = 1 for all y ∈ L: \1ᵃ, 2ᵇ, xᶜ\, except possibly when a ∈ \1,2\ and x is odd, \1ᵃ, xᵇ, (x+1)ᶜ\. This establishes that there are infinitely many sets U of size 3 for which there are infinitely many values of v where the BHR Conjecture holds for each multiset with support U. We also show that the BHR Conjecture holds for \1ᵃ,xᵇ,(x+1)ᶜ\ when x ∈ \7,9,10\ and (v,x) = (v,x+1) = 1.