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

Hamiltonian pathcomplete graphedge-length

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Cyclic Hamiltonian cycle systems of the \(\lambda \)-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
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• On a problem of Marco Buratti
• On perfect Γ-decompositions of the complete graph
• Spanning trees with specified differences in Cayley graphs

Cited in

(13)

• On a problem of Mariusz Meszka
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture
• On unitary/strong linear realizations: Buratti-Horak-Rosa conjecture
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• New methods to attack the Buratti-Horak-Rosa conjecture
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• Paths through equally spaced points on a circle
• A generalization of the problem of Mariusz Meszka
• Absolute differences along Hamiltonian paths
• A problem on partial sums in abelian groups
• A note on the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• A new proof for existence of horseshoe in the Rössler system

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)