Constructing Edge-labellings of $K_n$ with Constant-length Hamilton Cycles

Abstract

We present an optimal algorithm to label the edges of a complete graph with integer lengths so that every Hamilton cycle has the same length. The algorithm is complete in the sense that every edge-labelling with this property is the output labelling of some run of this algorithm. Such edge-labellings are induced by half-integer vertex-labellings by adding the vertex labels on an edge’s ends to determine its label. The Fibonacci sequence arises in this connection.