| Title | : | lamda - matchability in cubic graphs |
| Speaker | : | G S Santhosh Raghul (IITM) |
| Details | : | Mon, 24 Mar, 2025 3:30 PM @ SSB 334 |
| Abstract: | : | A connected graph with at least two vertices is considered matching covered if each of its edges is part of some perfect matching. Petersen (1891) demonstrated that every 2-connected 3-regular (cubic) graph possesses a perfect matching. Schonberger (1934) extended this result by proving that every such graph is also matching covered, a fact that follows directly from Tutte's 1-Factor Theorem (1947). Notably, a perfect matching can be viewed as a 1-regular spanning subgraph. Building on this idea, a v-matching is defined as a spanning subgraph in which a specific vertex v has degree three, while all other vertices have degree one. If such a subgraph exists, v is said to be lambda-matchable. Kral et al. (2009) utilized this concept to show that every 2-connected cubic graph with 2n vertices contains at least n perfect matchings. Inspired by this result, we sought to establish lower bounds on lambda(G), the number of lambda-matchable vertices in a 2-connected cubic graph G. Our findings leverage certain invariants introduced by Lovasz (1987). Specifically, Lovasz demonstrated that every matching covered graph can be uniquely decomposed into special matching covered subgraphs known as "bricks" (nonbipartite) and "braces" (bipartite). For any 2-connected cubic graph G, we establish the bound lambda(G) >= beta(G), where beta(G) represents the sum of the orders of the bricks in G. To develop our techniques, we examined lambda-matchability in bipartite graphs. A straightforward counting argument reveals that no vertex in a bipartite matching covered graph is lambda-matchable. Extending this idea, an (a, b)-matching is defined as a spanning subgraph where two designated vertices, a and b, have degree three, while all other vertices have degree one. If such a subgraph exists, the pair (a, b) is deemed lambda-matchable. We also establish a lower bound on the number of lambda-matchable pairs in any bipartite 2-connected cubic graph, expressed in terms of its braces. Our approach first addresses the 3-connected case before generalizing to 2-connected graphs using 2-cuts as an induction tool. Additionally, we characterize graphs that attain these lower bounds with equality, providing insight into their structural properties. |
