There is a well-known conjecture that all connected Cayley graphs are Hamiltonian. For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?

  • $\begingroup$ Not an answer, but: "Almost all Cayley graphs are Hamiltonian": Jixiang, Meng, and Huang Qiongxiang. Acta Mathematica Sinica 12.2 (1996): 151-155. $\endgroup$ Mar 20, 2014 at 23:18
  • $\begingroup$ I think that I did cubic Cayley graphs on up to 1000 vertices quite a few years ago, in the general hope that if any counterexample to the conjecture exists then cubic is the most likely place. $\endgroup$ Mar 21, 2014 at 0:13

1 Answer 1


According to : http://arxiv.org/pdf/1009.5795v3.pdf this is known for all n up to 120 except 72, 96, 108 and 120.

  • $\begingroup$ I've learned this has been checked to 1280 by Potocnik, Spiga and Verret, J. Symbolic Computation 50 (2013) 465-477. $\endgroup$ Mar 25, 2014 at 19:06
  • $\begingroup$ It has been checked to 1280 that, in the cubic vertex-transitive case, only the four well-known exceptions occur. The question asked for Cayley graphs of arbitrary valency. $\endgroup$
    – verret
    Mar 26, 2014 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.