Cubic graphs, perfect matchings and λ-matchability (by Santhosh Raghul) скачать в хорошем качестве

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.