Hamiltonicity of cubic Cayley graphs (Q2478599): Difference between revisions

Summary: Following a problem posed by Lovász 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)\)-presentation, that is, for groups \(G=\langle a,b\mid a^2=1, b^s=1, (ab)^3=1, \dots \rangle\) generated by an involution \(a\) and an element \(b\) of order \(s\geq3\) such that their product \(ab\) has order \(3\). More precisely, it is shown that the Cayley graph \(X=Cay(G,\{a,b,b^{-1}\})\) has a Hamilton cycle when \(|G|\) (and thus \(s\)) is congruent to \(2\) modulo \(4\), and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when \(|G|\) is congruent to \(0\) modulo \(4\).