Even Match Extendable Graph

Matching theory is at the core of graph theorv. Since it has important applications and is in connection with other theoretic problems closely, it has been studied extensively. And many celebrated results have been established, such as Hall's theorem and Tutte's theorem, characterizing thosc graphs with perfect matchings; Gallai-Edmonds structure theorem, a canonical decomposition theory of any graph in terms of its maximum matchings: the Hungarian method and Blossom algorithm, finding maximum weighted matchings of graphs. In the meantime, many typical topics arise, for example, matching polyhedra, elementary graphs, factor-critical graphs, enumeration of perfect matchings. Matching extendability, includingκ-extendability, IM-extendability, andκ-factor-criticality, is also one of them. Note that there is a close relation between k-factor-critical graphs andκ-extendable graphs: if a graph G is 2κ-factor-critical, then it isκ-extendable; and if a non-bipartite graph G isκ-extendable, whereκis even, then it isκ-factor-critical.Motivated by thc study ofκ-extendable graphs, IM-extendable graphs, andκ-factorcritical graphs, and by the fact that there are essential differences between matching problems of non-bipartite graphs and those of bipartite graphs, we propose a new notionbipartite matching extendable graphs. We say that a matching M of a graph G is a bipartite matching if G[V(M)] is a bipartite graph. We further say that G is bipartitematching extendable (BM-extendable in short) if every bipartite matching M of G is included in a perfect matching of G. Based on the following two aspects of motivation, BM-extendable graphs deserves an in-depth study.On the one hand, BM-extendable graphs have close relation with the other matching extendability:k-extendable(κ=m(G))=>BM-extendable=>IM-extendable=>1-extendable=>elementary,where m(G) is the cardinality of a maximum matching of G. In fact, our basic theorem "A BM-extendable graph is either bicritical or equilibrium decomposable" (see Chapter 2) indicates that the idea of BM-extendability can be traced back to those of factor critical graphs, bieritical graphs, and Gallai-Edmonds's decomposable structure. This reveals inherent relations of BM-extendability to classical matching theorem. Thus, any progress of the study of BM-extendability being obtained will contribute to the development of matching extendabilitv. Especially, it is significant to discover the evolvement from matching of bipartite graphs to that of non-bipartite graphs.On the other hand. BM-extendable graphs would have potential applications in chemistry. In quantum chemistry, a Kekule structure of a molecule graph G is a perfect matching M of G: a conjugated or resonant cycle is an M-alternating cycle. Note that a matching of a conjugated cycle is bipartite, and it is contained in a perfect matching of G. The notion of conjugated cycles has a close relation to BM-extendable graphs. In the known BM-extendable graphs, Clar number (the maximum number of their pairwise disjoint conjugated cycles) is large. So, the resonant energy of its corresponding molecule structure is as great as possible. From the view of the enumeration of Kekule structures, the molecule structures in this class are quite stable for the reason of their large number of perfect matchings.Except for some basic properties, the current study ofκ-extendable graphs, IMextendable graphs, andκ-factor critical graphs focus on the following aspects: structural properties, the connection with the parameters of graphs, the characterization of special graphs, extremal graph problems. Based on a systematic survey of the literatures of these topics, the study of BM-extendable graphs is also concentrated on the above main tasks. The present dissertation obtains five aspects of creative results as follows.1. ComplexityWe prove that the problem determining whether there is a bipartite matching of cardinalityκin a graph G is NP-complete; the problem determining whether a graph G is BM-extendable is co-NP-complete. For the polynomial solvable case, we present complete characterizations and decision algorithms of BM-extendability for bipartite graphs, complete multi-partite graphs, and 3-regular graphs, etc..2. Structural propertiesWe prove that BM-extendable graphs are 2-connected; obtain the sufficient and necessary conditions for BM-extendable graphs by Tutte's theorem; get some propcrtics of BM-extendable graphs about the operation of deleting vertices, deleting edges, contracting vertices, and expanding vertices. All these results are basic in the further study of BM- extendability.With regard to the relation between BM-extendable graphs and factor-critical graphs and bicritical graphs, we prove that if C is BM-extendable, then G is either bicritical or equilibrium decomposable. If G is equilibrium decomposable, then each component of G - S is factor-critical, where S is a maximal barrier of G. Moreover, for non-bicritical BM-extendable graph G, we obtain such a "bicriticality": if S is a maximal barrier of G. then for any vertices u∈S. v∈V(G) \ S, thereis a perfect matching in G - {n, v}. We also give a complete characterization of triangle-free equilibrium decomposable graphs.As for girth, we show that the girth of a BM-extendable graph is 3 or 4. We also give a sufficient condition about toughness for BM-extendability. Regarding necessity, for any rational number r, we can construct a BM-extcndable graph G of toughnessγ.3. Degree-type conditionsThe parameters related to degree -- maximum degree, degree sum, the maximum degree of two vertices -- are studied inκ-extendable graphs, IM-extendable graphs, andκ-factor-critical graphs. As for BM-extendable graphs, we also have a corresponding study, and obtain some degree-type results to determine BM-extendability of a graph. For general graphs, we give the conditions of the degree sum and minimum degree, and Fan-type condition. For claw-free graphs, we present the conditions of the degree sum and minimum degree. For regular and regular claw-free graphs, we get corresponding conditions. Moreover, we construct graphs to show that all the conditions obtained are best possible. From these we can see that BM-extendable graphs exist extensively in the class of comparatively dense graphs.4. 4-regular graphsThere was a complete characterization for claw-free 4-regular IM-extendable graphs in the literature. Base on a complicated argument, we present a complete characterization for 4-regular BM-extendable graphs: the only 4-regular BM-extendable graphs are the complete equitably bipartite graph K_4,4 and the strengthened cycle-ladder T_4n.5. Extremal graphsThe complete characterizatioin of maximal non-IM-extendable graphs, maximal nonκ-extendable, non-κ-factor-critical graphs, and maximal and minimalκ-extendable graphs (κk is 1, n, n - 1, where n is the number of vertices) have been alreadv obtained by several authors. In this dissertation, we give a complete characterization of maximal nonBM-extendable graphs, and find three families of maximal BM-extendable graphs: complete equitably bipartite graphs in the class of bipartite graphs, complete graphs in the class of complete multi-partite graphs, regular strengthened tree-ladders in the class of strengthened tree-ladders. For IM-extendable graphs, Yuan conjectured that maximal IMextendable non-bipartite graphs are only complete graphs with even number of vertices. The existence of maximal BM-extendable graphs -- regular strengthened tree-laddersimplies that this conjecture restricted to the class of BM-extendable graphs is not true. However, we prove that it is true within the familv of complete multi-partite graphs and those added some edges to them. About minimal BM-extendable graphs, we show that the complete equitably bipartite graphs and strengthened tree-ladders are minimal BMextendable. All these problems are with respect to the traditional partial order of edge inclusion.For another partial order -- teachability, the complete equitably bipartite graphs are no longer. maximal BM-extendable. In fact, we show that complete graph can be obtained from complete equitably bipartite graphs and BM-extendable multi-partite graphs by adding at most two edges each time, and the intermediate elements are also BMextendable.