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.
Ollis, M. A., Pasotti, A., Pellegrini, M. A., Schmitt, J. R., New methods to attack the Buratti-Horak-Rosa conjecture, <<DISCRETE MATHEMATICS>>, 2021; 344 (9): N/A-N/A. [doi:10.1016/j.disc.2021.112486] [http://hdl.handle.net/10807/182861]
New methods to attack the Buratti-Horak-Rosa conjecture
Pellegrini, Marco AntonioPenultimo
;
2021
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
