TY - JOUR
T1 - A new result on the problem of Buratti, Horak and Rosa
AU - Pasotti, Anita
AU - Pellegrini, Marco Antonio
PY - 2014
Y1 - 2014
N2 - The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of v−1 positive integers not exceeding [v/2] 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 the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of v, the number of multiples of d appearing in L is at most v−d. In this paper we do some preliminary discussions on the conjecture, including its relationship with graph decompositions. Then we prove, as main result, that the conjecture is true whenever all the elements of L are in {1,2,3,5}.
AB - The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of v−1 positive integers not exceeding [v/2] 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 the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of v, the number of multiples of d appearing in L is at most v−d. In this paper we do some preliminary discussions on the conjecture, including its relationship with graph decompositions. Then we prove, as main result, that the conjecture is true whenever all the elements of L are in {1,2,3,5}.
KW - Complete graph
KW - Edge-length
KW - Hamiltonian path
KW - Complete graph
KW - Edge-length
KW - Hamiltonian path
UR - http://hdl.handle.net/10807/55559
U2 - 10.1016/j.disc.2013.11.017
DO - 10.1016/j.disc.2013.11.017
M3 - Article
SN - 0012-365X
VL - 319
SP - 1
EP - 14
JO - Discrete Mathematics
JF - Discrete Mathematics
ER -