Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Giuseppe Mazzuoccolo (11.4.2024)

vo štvrtok 11.4.2024 o 9:50 hod. v posluchárni C

08. 04. 2024 15.18 hod.
Od: Martin Škoviera

Prednášajúci: Giuseppe Mazzuoccolo (University of Modena)

Názov: Non-double covered cubic graphs

Termín: 11.4.2024, 9:50 hod., poslucháreň C

Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. Actually, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. Here we study the class of non-double covered cubic graphs, i.e. graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass U of 3-connected cubic graphs. Then, we furnish an inductive characterization of U and we study properties related to the count of lonely edges. In particular, denoting by U_k the subclass of graphs of U with exactly k lonely edges, we prove that U_k is empty for k>6, and we present a complete characterization for k=3,4,5,6. We conclude with some insights on U_1 and U_2.


Stránka seminára