Hamiltonian cubic graphs
University of Modena and Reggio Emilia
University of Primorska and University of Ljubljana
Minisymposium: GENERAL SESSION TALKS
Content: A graph is Hamiltonian if it contains a spanning cycle (Hamiltonian cycle). A cubic Hamiltonian graph has a perfect matching (actually, three edge-disjoint perfect matchings). There are cubic graphs that have a perfect matching but are not Hamiltonian, see for instance the Petersen graph. Nevertheless, we may restrict our search for Hamiltonian graphs among the cubic graphs to the ones that possess a perfect matching. We give a necessary and sufficient condition for the existence of a Hamiltonian cycle in a cubic graph possessing a perfect matching. We use this condition to find a Hamiltonian cycle in some cubic graphs.