The Enumeration Problem Of Maximum Matchings And The Structure Of Some Specail Graphs

Let G be a simple graph with vertex set V(G) and edge set E(G). We say that aconnected graph G is factor - critical if G-v has a perfect matching for every vertexv∈V(G). Then a factor-critical graph G has odd vertices and its minimum degree is atleast two. If (?)x, y∈V(G), G-x-y has perfect matchings, G is said to be bicritical,it's clear that G is a bicritical graph if and only if for every vertex v∈V(G), G-vis factor-critical. A graph G is said to be claw-free if G does not contain any inducedsubgraph isomorphic to K_1,3. A cubic graph is a graph each vertex of which has degreethree.The problem of finding the number of maximum matchings and perfect matchingsof a graph plays an important role in graph theory and combinatorial optimization sinceit has a wide range of applications. For example, in the chemical context, the number ofperfect matchings of bipartite graphs is referred to as Kekuléstructure count[3, 4]. But theenumeration problem for maximum matchings in general graphs (even in bipartite graphs)is NP-hard[2]. In 2005, Liu yah characterize the structure of factor-critical graphs with thegiven number m(G)=|V(G)|+1. On this basis, in the second chapter, we characterizethe structure of factor-critical graphs with m(G)=|V(G)|+2. From this, some specialbicritical graphs are characterized. And in the third chapter, the perfect matching numberof no K₄-e contained claw-free cubic graphs is characterized.The main results of this thesis are following.Theorem2.10. Let G be a factor-critical graph with c blocks. Then m(G)=|V(G)|+2if and only if either1 all blocks of G are odd cycles but one, say such block H₁ and either H₁ is an etagraph E(l₁, l₂, l₃, l₄) satisfying that l₁=2, the path with length l₁ is a pending path of Gand the two ends of the path with length l₄ are connected by a pending path of G withlength 2, or H₁ is a theta graphΘ(l₁,l₂,l₃) satisfying l₁=4, and d_G(v₁)=d_G(v₃)=2,where the path with length l₁ is uv₁v₂v₃v, or 2 all blocks of G are odd cycles but two, say such blocks H₁ and H₂, H₁ and H₂ aretheta graphsΘ₁(l₁,l₂,l₃) andΘ₂(l₁′,l₂′,l₃′), respectively, satisfying that l₁=l₁′=2, thepath of H₁ with length l₁ and one of H₂ with length l₁′are both pending paths of G.Theorem 3.2. Let G be a claw-free cubic graph without k₄-e as it's induced sub-graphs and G is 2-connected with order n, then n=6k, k≥1 is integer, and the perfectmatching number of G is 2^k+1.