Some Results About Induced Matchings And Bipartite Matchings

The induced matching extendability and the bipartite matching extendability of graphs are two newly developed research topics in graph theory. The goals of their researches are revealing of the structure properties between the induced matchings (bipartite matchings) and the perfect matchings of graphs.A matching M of a graph G is called induced, if M together with the vertices incident to M form an induced subgraph of G, i.e., G[M]=G[V(M)]. A graph G is called induced matching extendable if every induced matching of G can be extended to a perfect matching of G. A matching M of a graph G is called bipartite, if the subgraph of G induced by the vertices incident to M is bipartite. A graph G is called bipartite matching extendable if every bipartite matching of G can be extended to a perfect matching of G.In this paper, we study the structure properties of induced matching extendable graph and bipartite matching extendable graphs. The main results of this paper are as follows.(1) Under some given conditions, the edge subdivision and vertex expanding keep the induced matching extendability of graphs.(2) The tight-cut decomposition keeps the bipartite matching extendability of graphs.(3) Study sufficient condition and necessary condition for the induced matching ex-tendability of graphs about toughness.(4) The induced matching extendability and the bipartite matching extendability are established on some special graphs, such as the complete multi-partitie graphs, T2, etc.(5) The maximal induced matching inextendable bipartite graphs are characterized.