Speaker
Roman Nedela
(University of West Bohemia)
Description
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, therefore
it is natural to investigate the hamiltonicity of cubic Cayley graphs. In general, no non-hamiltonian cubic $7$-cyclically connected graph except the Coxeter graph is known. This fact probably motivated C. Thomassen to state the following conjecture: If the cyclic connectivity of a cubic graph $X$ is large enough, then $X$ is hamiltonian. The conjecture can be strenghten as follows: Every 7-cyclically connected cubic graph except the Coxeter graph is hamiltonian. Since the cyclic connectivity of a vertex-transitive cubic graph is equal to the girth (Nedela, Skoviera 1995), there is a good motivation to investigate the hamiltonicity of vertex-transitive cubic graphs of girth at most six, an in particular, the cubic Cayley graphs of girth at most six. A small cycle in a Cayley graph implies a short relation in terms of generators, giving additional information on the base group. In the talk we use some results by Alspach and Maru\v si\v c to show that in most cases the cubic Cayley graphs of small girth are indeed hamiltonian, and we identify a few ``hard families'' of cubic Cayley graphs of small girth for which we are not able to verify the hamiltonicity.
The talk is based on a joint results done in collaboration with Elham Aboomahigir.
Primary author
Roman Nedela
(University of West Bohemia)
