Cubic graphs, perfect matchings and λ-matchability (by Santhosh Raghul)

Описание: This presentation comprises two parts; these correspond to the courses CS6999 and
CS7999 (at IIT-M CSE Dept.), respectively, and these are required for direct PhD scholars to acquire an MS degree on the way to their PhD.

In the first part, we shall discuss a couple of celebrated results pertaining
to cubic (that is, 3-regular) graphs from the literature, whereas the second part shall
focus on our contributions to further the understanding of cubic graphs.

(The two parts are unrelated except for the fact that they both pertain to cubic graphs, and heavily exploit the parity lemma that is stated in the beginning of the first part.)

Abstract for first part (CS6999):

Schönberger showed that each edge of a 2-connected cubic graph G lies in some
perfect matching; this inspires the following definition: the perfect matching index of G
is the least number of perfect matchings required to cover all edges. Berge conjectured
that the perfect matching index is at most five for all such graphs. Berge and Fulkerson
conjectured that every such graph admits a set of six (not necessarily distinct) perfect
matchings that covers each edge exactly twice.
It is easy to see that the Berge-Fulkerson Conjecture implies Berge’s Conjecture.
In literature, the former was often stated as a stronger version of the latter, until Mazzuoccolo
[J. Graph Theory, 2011] showed that these conjectures are in fact equivalent;
we shall discuss his proof.

Abstract for second part (CS7999):

A vertex v of a 2-connected cubic graph G is λ-matchable if G has a spanning
subgraph in which v has degree three whereas every other vertex has degree one, and
we let λ(G) denote the number of such vertices. Clearly, λ = 0 for bipartite graphs;
ergo, we define λ-matchable pairs analogously, and we let ρ(G) denote the number of
such pairs.
We improve the constant lower bounds on both λ and ρ established recently by
Chen, Lu and Zhang [Discrete Math., 2025] using matching-theoretic invariants arising
from the seminal work of Lovász [J. Combin. Theory Ser. B, 1987], and we characterize
all of the tight examples. We also solve the problem posed by Chen, Lu and Zhang:
characterize 2-connected cubic graphs that satisfy λ = n.