Hamiltonicity of cubic Cayley graphs

  • Henry H. Glover

    Ohio State University, Columbus, USA
  • Dragan Marusic

    University of Ljubljana, Slovenia

Abstract

Following a problem posed by Lov\'asz in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a (2,s,3)(2,s,3)-presentation, that is, for groups G=\laa,ba2=1,bs=1,(ab)3=1,\raG=\la a,b\mid a^2=1, b^s=1, (ab)^3=1, \dots \ra generated by an involution aa and an element bb of order s3s\geq3 such that their product abab has order 33. More precisely, it is shown that the Cayley graph X=Cay(G,{a,b,b1})X=Cay(G,\{a,b,b^{-1}\}) has a Hamilton cycle when G|G| (and thus ss) is congruent to 22 modulo 44, and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when G|G| is congruent to 00 modulo 44.

Cite this article

Henry H. Glover, Dragan Marusic, Hamiltonicity of cubic Cayley graphs. J. Eur. Math. Soc. 9 (2007), no. 4, pp. 775–787

DOI 10.4171/JEMS/96