Seminar of Graph Theory - Roman Nedela (22.3.2018)

Thursday 22.3.2018 at 9:50, Lecture room M/213

19. 03. 2018 17.04 hod.
By: Martin Škoviera

Roman Nedela (ZČU Plzen):
Hamilton cycles in cubic Cayley graphs and Thomassen's conjecture

Abstract:
Thomassen's conjecture claims the existence of a constant c such that every cubic graph of cyclic connectivity at least c is hamiltonian. In fact, the only known cyclically 7-connected cubic graph that is not hamiltonian is the Coxeter graph. In 1996, Nedela and Skoviera proved that for cubic vertex-transitive graphs the cyclic connectivity is equal to the girth. By a folklore conjecture, all cubic Cayley graphs are hamiltonian. Suppose that the Thomassen's conjecture holds for c=7. Then to prove hamiltonicity of the cubic Cayley graphs one needs to deal with graphs of girth at most six. The existence of small cycles in a Cayley graph put restrictions on the structure of the underlying group. In our talk we discuss the structure of the cubic Cayley graphs of girth at most six and in many cases show their hamiltonicity. The remaining "hard cases" will be described.