Vortrag fällt aus
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.
If you are interested in participating online (either regularly or only in a specific lecture), please contact Yulai Ma or Eckhard Steffen in advance so that the participation link can be shared.