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)

• 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
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• On Hamiltonian paths with prescribed edge lengths in the complete graph
• New methods to attack the Buratti-Horak-Rosa conjecture
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• On unitary/strong linear realizations: Buratti-Horak-Rosa conjecture
• A problem on partial sums in abelian groups
• On a problem of Mariusz Meszka
• A generalization of the problem of Mariusz Meszka
• Paths through equally spaced points on a circle
• Absolute differences along Hamiltonian paths
• 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)