1
$\begingroup$

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)?

$\endgroup$
2
  • $\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$ – Joseph O'Rourke Mar 20 '14 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$ – Gordon Royle Mar 21 '14 at 0:13
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I've learned this has been checked to 1280 by Potocnik, Spiga and Verret, J. Symbolic Computation 50 (2013) 465-477. $\endgroup$ – user39684 Mar 25 '14 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 '14 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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