2024/02/13 by Onur Ağırseven, Agirseven, Onur, M. A. Ollis +1
Computer Science · #05C38 #05C78 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2402.08736
openalex publication_date 2024/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Label the vertices of the complete graph Kv with the integers \0, 1, …, v-1\ and define the \em length ℓ of the edge between distinct vertices labeled x and y by ℓ(x,y) = min( |y-x|, v - |y-x| ). A \em realization of a multiset L of size v-1 is a Hamiltonian path through Kv whose edge labels are L. The \em 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 Conjecture holds 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.