Lifting Hamilton cycles of quotient graphs (Q914699): Difference between revisions

The problem of determining whether or not every Cayley graph has a Hamilton cycle is the subject of a recent survey paper by \textit{D. Witte} and \textit{J. A. Gallian} [ibid. 51, 293-304 (1984)]. Among the unsolved problems listed there is that of deciding whether the Cayley graph on the semidirect product of two cyclic groups with the standard generators has a Hamilton cycle. This problem is settled here through the use of quotient graphs which arise as follows. A permutation \(\alpha\) is said to be semiregular if the group \(<\alpha >\) generated by \(\alpha\) is semiregular, i.e., if all cycles in the disjoint cycle decomposition of \(\alpha\) have the same length. If G is a graph and the group of automorphisms on G contains a semiregular element \(\alpha\), then there is a natural quotient graph G/\(\alpha\) the vertices of which are the orbits of \(<\alpha >\) and two such vertices are adjacent iff there is an edge in G joining a vertex of one corresponding orbit to a vertex in the other corresponding orbit.