GENERATING HAMILTONIAN CYCLES IN COMPLETE GRAPHS
Herbert Fleischner · 1993
. We prove that hamiltonian cycles of complete graphs can be generated in a Gray code manner by means of small local interchanges. 1. Introduction Let C and C 0 be two hamiltonian cycles in a (simple) graph G. We say that C and C 0 are switching-equivalent (symbolically, C C 0 ) if the symmetric difference of their edge sets induces a quadrangle in G, i.e., if E(C) 4 E(C 0 ) = fa; b; c; dg where a; b; c; d are the consecutive edges of a cycle of length 4 in G. It is easy to see that C C 0 if and only if the cyclic sequences of vertices representing C and C 0 have the form C = (u 1 u 2 v 1 : : : v k u 3 u 4 w 1 : : : wm ), C 0 = (u 1 u 3 v k : : : v 1 u 2 u 4 w 1 : : : wm ); in this case E(C) 4 E(C 0 ) is the edge set of the quadrangle u 1 u 2 u 4 u 3 in G. Roughly speaking, C 0 is then obtained from C by "switching" the pairs of edges u 1 u 2 , u 3 u 4 and u 1 u 3 , u 2 u 4 . If k = 0, i.e., if C = (u 1 u 2 u 3 u 4 : : : ) and C 0 = (u 1 u 3 u 2 u 4 : : : ), th...