Some Results On Maximum Matchings Of Graphs

The study on the maximum matchings (as well as perfect matchings) of a graph plays a central role in matching theory. In addition to the algorithnis of finding maximum matchings, the structural properties of all maximum matchings are significant in theory or application aspect. Roughly speaking, the properties we are concerned in this thesis are mainly as follows:1.How many maximum matchings are there in a graph?2.How are they transformed from each other?3.How are they growing from smaller matchings?In other words, we shall concentrate ourselves on the enumeration, the transformation graph and the extendability of maximum matchings. The organization of the thesis is as follows.In the first chapter, we list some terminologies, notations and introduce some topics about matching theory. In the second chapter, some results about the number of maximum matchings are presented. In the third chapter, the maximum matching graph of a graph is characterized. In the fourth chapter, we give degree conditions of induced matchingextendable graphs and conditions of a matching and a maximum matching being an induced one, respectively, and obtain some results about matching extendability.Number of Maximum MatchingsThe research on the number of perfect matchings can be found in many articles [11-14]. But not many results about the number of maximum matchings are known( even in bipartite graphs). In this part, some1results about this topic are presented. Firstly, We give some good lower bounds of the number.Theorem 1. Let G = (A, B) be a connected bipartite graph with positive surplus( as viewed from A). Then G has at least IE(G)I + (jAj ?1) * (def(G) ?2) maximum matchings.Theorem 2. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree at least 2. Then G contains at least 2jE(G)j ?21B1 near-perfect matchings.Theorem 3. Let G be a factor-critical graph. Then G has at least IE(G)I ?c)~near-perfect matchings, where c is the number of utverticesof C.~?bLocksThe enumeration problems for maximum matchings on some special graphs are solved.Theorem 4. Let C = (A, B) is a bipartite graph with positive surplus( as viewed from A) and deficiency 1. Then the following are equivalent:(i)Every vertex of A has degree 2;(ii)G is a tree;(iii) Every vertex of A is a barrier of G;(iv) C kas exactly IAI + 1 near-perfect matchings;(v)C ?v has a unique perfect matching for any vertex v C B.Theorem 5. Let C = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree 1. Then G has exactly ~E(G)j ?IAI + 1 near-perfect matchings if and only if there exists a vertex in NG(u) with degree 1 for any vertex u in A with degree at least 3.Theorem 6. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and dG(v) = 2 for each vertex v in B. Then G has exactly 2jBI + 2m near-perfect matchings, where m is the number of cut vertices in B.Theorem 7. Let C be a 2-connected factor-critical graph. Then2G has precisely IE(G) near-perfect matchings if and only if there existsan ear decomposition of G starting with a nice odd cycle C; that is,G = C + P1 + ... ?Pk satisfying that P~ is open and two ends of P1 areconnected in G~1 by a pending path with length 2 of G for 1