New methods to attack the Buratti-Horak-Rosa conjecture

DOI10.1016/J.DISC.2021.112486MaRDI QIDQ2037561zbMATH OpenOpenAlexWikidataFDO

Authors M. A. Ollis, Anita Pasotti, Marco Antonio Pellegrini, John Schmitt

Publication date 8 July 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian pathcomplete graphedge-lengthgraceful permutationlinear realization

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $leftlfloorfracv2ightfloor$ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set $0,1,ldots,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,ldots,2x$, $1,2,4,ldots,2x,2x+1$. We also consider lists with many consecutive elements.

Recommendations

• A new result on the problem of Buratti, Horak and Rosa
• 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
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• On Hamiltonian paths with prescribed edge lengths in the complete graph

Cites work

• scientific article; zbMATH DE number 3435497 (Why is no real title available?)
• scientific article; zbMATH DE number 7283876 (Why is no real title available?)
• A generalization of the problem of Mariusz Meszka
• A new result on the problem of Buratti, Horak and Rosa
• A problem on partial sums in abelian groups
• Absolute differences along Hamiltonian paths
• Dihedral Hamiltonian cycle systems of the cocktail party graph
• Distinct partial sums in cyclic groups: polynomial method and constructive approaches
• 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 generalization of the seating couples problem
• On a problem of Marco Buratti
• On a problem of Mariusz Meszka
• On partial sums in cyclic groups
• On perfect Γ-decompositions of the complete graph
• On strongly sequenceable abelian groups
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• Partitions of nonzero elements of a finite field into pairs
• Seating couples around the king's table and a new characterization of prime numbers
• Sequenceable groups and related topics.
• Some new results about a conjecture by Brian Alspach
• The wonderful Walecki construction

Cited in

(8)

• A new result on the problem of Buratti, Horak and Rosa
• 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
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• On unitary/strong linear realizations: Buratti-Horak-Rosa conjecture
• Paths through equally spaced points on a circle

This page was built for publication: New methods to attack the Buratti-Horak-Rosa conjecture

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