Cubic graphs with perfect 1-factorizations (Seminar DM)

Iz MaFiRaWiki

Cubic graphs with perfect 1-factorizations

Simona Bonvicini, Department of Science and Methods of Engineering, University of Modena and Reggio Emilia, Italy

Torek, 17. januar 2012, od 10-12, Plemljev seminar, Jadranska 19

Povzetek: A regular graph G is perfectly 1-factorable (P1F, for short) if it possesses a 1-factorization \mathcal F such that the union of any two 1-factors of \mathcal 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.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja