TY - JOUR

T1 - New methods to attack the Buratti-Horak-Rosa conjecture

AU - Pellegrini, Marco Antonio

AU - Ollis, M. A.

AU - Pasotti, Anita

AU - Schmitt, John R.

PY - 2021

Y1 - 2021

N2 - The conjecture, still widely open, posed by Marco Buratti, Peter Horak and Alex Rosa states that a list L of v−1 positive integers not exceeding ⌊[Formula Presented]⌋ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set {0,1,…,v−1} if and only if, for every divisor d of v, the number of multiples of d appearing in L is at most v−d. In this paper we present new methods that are based on linear realizations and can be applied to prove the validity of this conjecture for a vast choice of lists. As example of their flexibility, we consider lists whose underlying set is one of the following: {x,y,x+y}, {1,2,3,4}, {1,2,4,…,2x}, {1,2,4,…,2x,2x+1}. We also consider lists with many consecutive elements.

AB - The conjecture, still widely open, posed by Marco Buratti, Peter Horak and Alex Rosa states that a list L of v−1 positive integers not exceeding ⌊[Formula Presented]⌋ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set {0,1,…,v−1} if and only if, for every divisor d of v, the number of multiples of d appearing in L is at most v−d. In this paper we present new methods that are based on linear realizations and can be applied to prove the validity of this conjecture for a vast choice of lists. As example of their flexibility, we consider lists whose underlying set is one of the following: {x,y,x+y}, {1,2,3,4}, {1,2,4,…,2x}, {1,2,4,…,2x,2x+1}. We also consider lists with many consecutive elements.

KW - Complete graph

KW - Edge-length

KW - Graceful permutation

KW - Hamiltonian path

KW - Linear realization

KW - Complete graph

KW - Edge-length

KW - Graceful permutation

KW - Hamiltonian path

KW - Linear realization

UR - http://hdl.handle.net/10807/182861

U2 - 10.1016/j.disc.2021.112486

DO - 10.1016/j.disc.2021.112486

M3 - Article

VL - 344

SP - N/A-N/A

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -