Absolute Differences Along Hamiltonian Paths

Francesco Monopoli


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.


Hamiltonian paths

Full Text: PDF