A new result on the problem of Buratti, Horak and Rosa

DOI10.1016/J.DISC.2013.11.017MaRDI QIDQ394341zbMATH OpenOpenAlexFDO

Authors Anita Pasotti, Marco Antonio Pellegrini

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.6482

zbMATH Keywords

complete graphedge-lengthHamiltonian path

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: 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}.

Recommendations

• New methods to attack the Buratti-Horak-Rosa conjecture
• A note on the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture

Cites work

• Cyclic Hamiltonian cycle systems of the -fold complete and cocktail party graphs
• Dihedral Hamiltonian cycle systems of the cocktail party graph
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• On a problem of Marco Buratti
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• On perfect Γ-decompositions of the complete graph
• Spanning trees with specified differences in Cayley graphs

Cited in

(16)

• A new proof for existence of horseshoe in the Rössler system
• A problem on partial sums in abelian groups
• New methods to attack the Buratti-Horak-Rosa conjecture
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• On a problem of Mariusz Meszka
• Absolute differences along Hamiltonian paths
• A note on the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture
• Paths through equally spaced points on a circle
• A generalization of the problem of Mariusz Meszka
• On unitary/strong linear realizations: Buratti-Horak-Rosa conjecture
• The Buratti-Horak-Rosa conjecture holds for some underlying sets of size three
• Circulant TSP: vertices of the edge-length polytope and superpolynomial lower bounds
• Circulant TSP special cases: easily-solvable cases and improved approximations

This page was built for publication: A new result on the problem of Buratti, Horak and Rosa

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394341)