Hamiltonicity of Cubic Cayley Graphs

Original · EN

Following a problem posed by Lovász in 1969, it is believed that every connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from groups having a (2,s,3)-presentation, that is, for groups G= a,b| a²=1, bˢ=1, (ab)³=1, etc. generated by an involution a and an element b of order s≥3 such that their product ab has order 3. More precisely, it is shown that the Cayley graph X=Cay(G,{a,b,b⁻¹}) has a Hamilton cycle when |G| (and thus s) is congruent to 2 modulo 4, and has a long cycle missing only two vertices (and thus necessarily a Hamilton path) when |G| is congruent to 0 modulo 4.