Home > News > Simona Bonvicini: Cubic graphs with perfect 1-factorizations

Simona Bonvicini: Cubic graphs with perfect 1-factorizations

Date: 15. 1. 2012
Source: Discrete mathematics seminar
Torek, 17. 1. 2012 od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek: A regular graph G is perfectly 1-factorable (P1F, for short) if it possesses a 1-factorization F such that the union of any two 1-factors of F is a Hamiltonian cycle.

In 1962, Kotzig described a procedure to obtain all perfectly 1-factorable cubic graphs starting from the θ-graph (the graph consisting of two vertices and three multiple edges between them). Unfortunately, his procedure does not tell whether a cubic graph G is P1F or not. For this reason, we investigate some large families of cubic graphs and give some properties of P1F cubic graphs. We also show an alternative proof of Kotzig's result.

This is joint work with Giuseppe Mazzuoccolo.