Bipartite Matching-extendability Of Special Graphs

Matching theory is at the core of graph theory. Since it has important applicationsand is in connection with other theoretic problems closely, it has been studied exten-sively. And many celebrated results have been established, for example, Hall's theoremand Tutte's theorem, characterizing those graphs with perfect matchings; Gallai-Edmondsstructure theorem, a canonical decomposition theory of any graph in terms of its max-imum match- ings; the Hungarian method and Blossom algorithm, finding maximumweighted matchings of graphs. In the meantime, many typical topics arise, for exam-ple, matching polyhedra, elementary graphs, factor-critical graphs, enumeration of per-fect matchings. Matching extendability, including k-extendability, IM-extendability, andk-factor-criticality, is also one of them. Note that there is a close relation between k-factor-critical graphs and k-extendable graphs: if a graph G is 2k-factor-critical, then itis k-extendable; and if a non-bipartite graph G is k-extendable, where k is even, then itis k-factor-critical.Motivated by the study of k-extendable graphs, IM-extendable graphs, and k-factor-critical graphs,and by the fact that there are essential di?erences between matchingproblems of non-bipartite graphs and those of bipartite graphs, X.M. Wang [1] propose anew notion―bipartite matching extendable graphs in 2005. We say that a matching Mof a graph G is a bipartite matching if G[V (M)] is a bipartite graph. We further say thatG is bipartite-matching extendable (BM-extendable in short) if every bipartite matchingM of G is included in a perfect matching of G. Based on the following two aspects ofmotivation, BM-extendable graphs deserves an in-depth study.On the one hand, BM-extendable graphs have close relation with the other matchingextendability:where m(G) is the cardinality of a maximum matching of G. In fact, any progress of thestudy of BM-extendability being obtained will contribute to the development of matchingextendability. Especially, it is significant to discover the evolvement from matching ofbipartite graphs to that of non-bipartite graphs.On the other hand, BM-extendable graphs would have potential applications in chem-istry. In quantum chemistry, a Kekul′e structure of a molecule graph G is a perfectmatching 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 matchingof G. The notion of conjugated cycles has a close relation to BM-extendable graphs. Inthe known BM-extendable graphs, Clar number (the maximum number of their pairwisedisjoint conjugated cycles) is large. So, the resonant energy of its corresponding moleculestructure is as great as possible. From the view of the enumeration of Kekul′e structures,the molecule structures in this class are quite stable for the reason of their large numberof perfect matchings.Except for some basic properties, the current study of k-extendable graphs, IM-extendable graphs, and k-factor critical graphs focus on the following aspects: structuralproperties, the connection with the parameters of graphs, the characterization of specialgraphs, extremal graph problems. Based on a systematic survey of the literatures of thesetopics, the study of BM-extendable graphs is also concentrated on the above main tasks.The present dissertation obtains several aspects of creative results as follows.1. Bipartite matching extendability of Halin graphsWe prove that the problem determining whether there is a bipartite matching-extendability in a Halin graph G, and obtain the su?cient and necessary conditions.The main result of this section is as follows: Halin graph H = (T C) is BM-extendableif and only if its characteristic tree T is isomorphic to K1,3, K1,5 or K1,7.2. Structural properties of K1,3-free bicritical BM-extendable graphsWe prove that any bicritical BM-extendable graph G, if {u,v} is a vertex cut of G,then u is adjacent to v. The K1,3-free bicritical BM-extendable graph G is 3-connected.Any K1,3-free bicritical BM-extendable graph G, let {x,y,z} of G be a vertex cut. Then:(i) the vertex cut {x,y,z} is independent set, (ii) G ? {x,y,z} has exactly two compo-nents, odd component G1 with |V (G1)| = 1, and even component G2 with |V (G2)|≥6.All these results are basic in the further study of BM-extendability.With regard to the relation between BM-extendable graphs and factor-critical graphsand bicritical graphs, X.M. Wang prove that if G is BM-extendable, then G is eitherbicritical or equilibrium decomposable. If G is equilibrium decomposable, then eachcomponent of G ? S is factor-critical, where S is a maximal barrier of G.