Every finite (2, s, 3) Cayley graph is Hamiltonian
by
Henry Glover
Ohio State University
Coauthors: D. Marusic

We prove that the Cayley graph of every finite group presentation of the form < a, x|a²=x^s=(ax)³=1, etc. > has a Hamilton cycle. In three out of four cases we do this by showing that the associated Cayley map has a (Hamilton) tree of faces with the property that every vertex of the original Cayley graph is on the boundary of at least one of these faces. The boundary of the resulting topological disk is the desired Hamilton cycle. In the fourth case we need to pass to the Z/2-quotient surface to get this Hamilton tree and then lift an associated singular cycle (not the boundary of this topolgical disk in the quotient surface) to the desired Hamilton cycle. We note that most finite simple groups have presentations to which our result applies. (In fact, our methods show every finite simple group has some presentation with Hamiltonian Cayley graph.)

Date received: November 9, 2000