Zóna pre zamestnancov
a študentov FMFI UK

Seminár z teórie grafov - Martin Škoviera (2.3.2017)

vo štvrtok 2.3.2017 o 9:50 hod. v miestnosti M/213


27. 02. 2017 14.19 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Hamilton cycles in embedded cubic graphs

Termín: 2.3.2017, 9:50 hod., M/213

Abstrakt:
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.