Cubic Cayley graphs of girth at most six and their hamiltonicity

Abstract

In 1969 Lov\' asz conjectured that a vertex-transitive graph admits a Hamilton path.
In fact, only $5$ non-hamiltonian vertex-transitive graphs are known, namely $K_2$, the Petersen and the Coxeter graphs and their truncations. This motivates a folklore conjecture stating that every Cayley graph is hamiltonian. Moreover, four of the five examples are cubic graphs.
In this article we investigate the conjecture for the cubic Cayley graphs
of girth at most $6$. In general, no non-hamiltonian cubic cyclically $7$-connected graph except the Coxeter graph is known. Note that the cyclic
connectivity of a cubic graph is bounded by the girth, and it was proved
in 1995 by Nedela and \v{S}koviera that for the vertex-transitive cubic graphs the girth equals the cyclic connectivity. The fact that all known non-hamiltonian cubic graphs have cyclic connectivity bounded by $7$ probably motivated Thomassen to formulate the following conjecture: If the cyclic connectivity of a cubic graph $X$ is large enough, then $X$ is hamiltonian. Even the following strong conjecture could hold: A cyclically $7$-connected cubic graph is hamiltonian, or it is the Coxeter graph. Assuming the conjecture holds true, to confirm the folklore conjecture for cubic Cayley graphs it is sufficient to verify it for cubic Cayley graphs of girth at most $6$.
In this paper we characterise cubic Cayley graphs of girth at most six and identify few ``hard families'' of cubic Cayley graphs of small girth for which we are not able to verify whether they are hamiltonian.