Absolute differences along Hamiltonian paths

MaRDI QIDQ490402zbMATH OpenFDO

Authors Francesco Monopoli

Publication date 27 August 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0799, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hamiltonian paths

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: Given a set $A$ of real numbers consider the complete graph on the elements of $A$. We prove that if $A$ is an arithmetic progression then for every vertex $ainA$ there exists an hamiltonian path such that the absolute differences of consecutive vertices are pairwise distinct. This result partially proves a conjecture by Zhi-Wei Sun.

Review text

Summary: We prove that if the vertices of a complete graph are labeled with the elements of an arithmetic progression, then for any given vertex there is a Hamiltonian path starting at this vertex such that the absolute values of the differences of consecutive vertices along the path are pairwise distinct. In another extreme case where the label set has small additive energy, we show that the graph actually possesses a Hamiltonian cycle with the property just mentioned. These results partially solve a conjecture by \textit{Z.-W. Sun} [``Some new problems in additive combinatorics, Preprint, \url{arXiv:1309.1679}].

Recommendations

• Hamiltonian paths in distance graphs
• On Hamiltonian paths in distance graphs
• On mutually independent Hamiltonian paths
• Hamiltonian square-paths
• scientific article; zbMATH DE number 438460
• Hamiltonian paths in infinite graphs
• On Hamiltonian paths and a chain metric
• On Hamiltonian alternating cycles and paths
• Sums and differences along Hamiltonian cycles
• Sums and differences along Hamiltonian cycles

Cites work

• A new result on the problem of Buratti, Horak and Rosa
• On a problem of Marco Buratti
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• Sums and differences along Hamiltonian cycles

Cited in

(7)

• New methods to attack the Buratti-Horak-Rosa conjecture
• scientific article; zbMATH DE number 6850346 (Why is no real title available?)
• scientific article; zbMATH DE number 2159648 (Why is no real title available?)
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture
• Sums and differences along Hamiltonian cycles
• Sums and differences along Hamiltonian cycles
• On unitary/strong linear realizations: Buratti-Horak-Rosa conjecture

This page was built for publication: Absolute differences along Hamiltonian paths

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