| Title | : | Equivalence classes, solitary patterns and cubic graphs |
| Speaker | : | D V V Narayana (IIT-M) |
| Details | : | Thu, 19 Sep, 2024 3:30 PM @ SSB 134 |
| Abstract: | : | Extensive research has been conducted on 2-connected cubic (3-regular) graphs. Petersen (1891) proved that every 2-connected cubic graph has a perfect matching; and Sch ̈onberger (1934) showed that each edge in a 2-connected cubic graph is part of some perfect matching. In light of these well-known results, we set out to characterize those 2-connected cubic graphs in which every edge is part of at least two perfect matchings. An edge is refered to as a solitary edge if it belongs to a unique perfect matching. Thus, we can restate our objective as characterizing all 2-connected cubic graphs that do not contain any solitary edges. In the case of 2-connected graphs, there are graphs with n 2 solitary edges, where n is the number of vertices. The problem turns out to be more interesting in the case of 3-connected graphs. A connected graph G with two or more vertices is matching covered if each edge is part of at least one perfect matching. The concept of dependency rela- tionship between edges, in a matching covered graph, was formally introduced and studied by Carvalho, Lucchesi and Murty (1999). Two edges are mutually dependent if every perfect matching containing either of them also contains the other. Clearly, this is an equivalence relation and thus induces a partition of the edge set; each part is refered to as an equivalence class. Observe that n 2 is an upper bound on the cardinality of any equivalence class. We provide a characterization of those matching covered graphs that attain this upper bound. It is worth noting that if any member of an equivalence class is solitary then so is every member; we refer to such an equivalence class as a solitary class. This immediately leads us to the notion of solitary pattern of a matching covered graph — the sequence of cardinalities of its solitary classes in nonincreasing order. For instance, K4 has solitary pattern (2, 2, 2) whereas the Petersen graph has solitary pattern (). Using the theory developed by Carvalho, Lucchesi and Murty, we prove that every 3-connected cubic graph G has one of the following ten solitary pat- terns: (2, 2, 2), (2, 2, 1), (2, 2), (2, 1, 1), (2, 1), (2), (1, 1, 1), (1, 1), (1) or (); con- sequently, G has at most six solitary edges. We also provide characterizations of 3-connected cubic graphs that have a fixed solitary pattern except for (1, 1), (1) and (). Finally, we deduce that every 2-connected cubic graph, except for θ, K4, C6 and the bicorn graph, has at most n 2 solitary edges, and equality holds if and only if its solitary edges comprise a solitary class (that is a perfect match- ing). This is joint work with Kalyani Gohokar (CMI) and Nishad Kothari, and has been submitted to a journal; the manuscript is available here: https://arxiv. org/abs/2409.00534. |
