Absolute Differences Along Hamiltonian Paths

  • Francesco Monopoli
Keywords: Hamiltonian paths

Abstract

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 Z.-W. Sun.
Published
2015-08-14
Article Number
P3.20