TY - JOUR
T1 - Growable realizations: a powerful approach to the Buratti-Horak-Rosa Conjecture
AU - Ollis, M. A.
AU - Pasotti, Anita
AU - Pellegrini, Marco Antonio
AU - Schmitt, John R.
PY - 2022
Y1 - 2022
N2 - Label the vertices of the complete graph Kv with the integers {0, 1, . . ., v − 1} and define the length of the edge between the vertices 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, . . ., ⌊v/2⌋}. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in Kv 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
AB - Label the vertices of the complete graph Kv with the integers {0, 1, . . ., v − 1} and define the length of the edge between the vertices 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, . . ., ⌊v/2⌋}. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in Kv 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
KW - Hamiltonian path
KW - complete graph
KW - edge-length
KW - growable realization
KW - Hamiltonian path
KW - complete graph
KW - edge-length
KW - growable realization
UR - http://hdl.handle.net/10807/214984
U2 - 10.26493/1855-3974.2659.be1
DO - 10.26493/1855-3974.2659.be1
M3 - Article
SN - 1855-3966
VL - 22
SP - N/A-N/A
JO - Ars Mathematica Contemporanea
JF - Ars Mathematica Contemporanea
ER -