Seminar of Graph Theory - Martin Škoviera (2.3.2017)

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

---

Martin Škoviera:
Hamilton cycles in embedded cubic graphs

Abstract:
In this talk we develop the idea that embedding a cubic graph into a closed surface can serve as a convenient tool for finding a Hamilton cycle in it. We establish a necessary and sufficient condition for a cubic graph embedded in a closed surface, orientable or not, to have a bounding Hamilton cycle. With this characterisation and its consequences we can guarantee Hamilton cycles in wide classes of cubic graphs. Among others, we provide a unified and relatively short proof of a result due to Glover, Marusic, Kutnar, and others proved in a series of four papers published over the years 1996-2012 that cubic Cayley graphs of finite quotients of the modular group have a Hamilton path and, except in one special case, they also have a Hamilton cycle. We further show that in the remaining case these graphs have no bounding Hamilton cycle.

This is a joint work with Roman Nedela.

---