Absolute differences along Hamiltonian paths (Q490402): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / 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}]. | |||
| Property / 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}]. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C38 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 6476274 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
Hamiltonian paths | |||
| Property / zbMATH Keywords: Hamiltonian paths / rank | |||
Normal rank | |||
Revision as of 21:36, 30 June 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Absolute differences along Hamiltonian paths |
scientific article |
Statements
Absolute differences along Hamiltonian paths (English)
0 references
27 August 2015
0 references
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}].
0 references
Hamiltonian paths
0 references
