Cubic Cayley graphs of girth at most six and their hamiltonicity
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 2, pp. 351-359
Elham Aboomahigir; Roman Nedela; Elham Aboomahigir; Roman Nedela. Cubic Cayley graphs of girth at most six and their hamiltonicity. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 2, pp. 351-359. http://geodesic.mathdoc.fr/item/AMUC_2019_88_2_a14/
@article{AMUC_2019_88_2_a14,
     author = {Elham Aboomahigir and Roman Nedela and Elham Aboomahigir and Roman Nedela},
     title = { Cubic {Cayley} graphs of girth at most six and their hamiltonicity},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {351--359},
     year = {2019},
     volume = {88},
     number = {2},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_2_a14/}
}
TY  - JOUR
AU  - Elham Aboomahigir
AU  - Roman Nedela
AU  - Elham Aboomahigir
AU  - Roman Nedela
TI  - Cubic Cayley graphs of girth at most six and their hamiltonicity
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 351
EP  - 359
VL  - 88
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_2_a14/
ID  - AMUC_2019_88_2_a14
ER  - 
%0 Journal Article
%A Elham Aboomahigir
%A Roman Nedela
%A Elham Aboomahigir
%A Roman Nedela
%T Cubic Cayley graphs of girth at most six and their hamiltonicity
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 351-359
%V 88
%N 2
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_2_a14/
%F AMUC_2019_88_2_a14

Voir la notice de l'article provenant de la source Comenius University

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.