Label the vertices of the complete graph $K_v$ with the integers ${ 0, 1, ldots, v-1 }$ and define the length of the edge between $x$ and $y$ to be $min( |x-y| , v - |x-y| )$. Let $L$ be a multiset of size $v-1$ with underlying set contained in ${ 1, ldots, lfloor v/2 rfloor }$. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in $K_v$ whose edge lengths are exactly $L$ if and only if for any divisor $d$ of $v$ the number of multiples of $d$ appearing in $L$ is at most $v-d$. We introduce growable realizations, which enable us to prove many new instances of the conjecture and to reprove known results in a simpler way. As examples of the new method, we give a complete solution when the underlying set is contained in ${ 1,4,5 }$ or in ${ 1,2,3,4 }$ and a partial result when the underlying set has the form ${ 1, x, 2x }$. We believe that for any set $U$ of positive integers there is a finite set of growable realizations that implies the truth of the Buratti-Horak-Rosa Conjecture for all but finitely many multisets with underlying set $U$.
Download