Seminar of Graph Theory - Giuseppe Mazzuoccolo (11.4.2024)
Thursday 11.4.2024 at 9:50, Lecture room C
Giuseppe Mazzuoccolo (University of Modena):
Non-double covered cubic graphs
Abstract:
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.