Some Conclusions On Bipartite Matching Of Graph

Graphs considered in this paper are simple,finite,undirected and connected.In this paper,research on a number of some sex-related questions of bipartite matching extendability of graph theory,by the following four components:(ⅰ) Introduction to matching theory,and the progress and the study of bipartite matching extendable graphs.(ⅱ) Degree conditions of 2κ-vertex deletable andκ-edge deletable BM- extendable.(ⅲ) Bipartite matching extendability of Harary graphs.(ⅳ) n-bipartite matching extendable graphs.Matching theory is at the core of graph theory.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,for example,Hall's theorem and Tutte's theorem,characterizing those 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.A matching M of G is an induced matching if E(V(M))=M,researchs on induced matching may be found in(Cameron,1989)[4].Many results on induced matching can be found in[4,5,6,11,16].J.J.Yuan propose a new notion—induced matching extendable graphs in 1998140].G is said to be induced matching extendable(IM-extendable in short) if every induced matching M extends to a perfect matching.Motivated by the 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,X.M.Wang propose a new notion—bipartite matching extendable graphs in 2005[33].We say that a matching M of a graph G is a bipartite matching if G[V(M)]is a bipartite graph(containing no odd cycles).We further say that G is bipartite-matching extendable(BM-extendable in short) if every bipartite matching M of G is included in a perfect matching of G.It is obvious that every BM-extendable graph must have an even number of vertices.We can also easily see that the complete graphs K_2m and complete bipartite graphs K_m,m are BM-extendable, but K_m,m -e is not BM-extendable for any edge e in K_m,m.The only BM-extendable path and cycle are P₂ and C₄,respectively.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 several aspects of creative results as follows.G is called a 2κ-vertex deletable BM-extendable graph,if G - S is BM-extendable for every S(?) V(G) with |S|=2κ.For any simple and connected graphs G with V(G)= 2n,n≥3,ifδ(G)≥(3n+κ)/2,then G is 2κ-vertex deletable BM-extendable.Where k is positive integer less than or equal to n-2.In addition,for[(3n+κ)/2]is the smallest positive integerδ,ifδ(G)≥δ,then G is 2κ-vertex deletable BM-extendable.Graphs G is a simple and connected with V(G) = 2n,G is called aκ-edge deletable BM-extendable graph,if G - F is BM-extendable for every F(?) E(G) with |F|=κ.For any simple and connected graphs G with V(G) = 2n,ifδ(G)≥3n/2 +κ/2,then G isκ-edge deletable BM-extendable,where n≥3,[κ/2]≤[3n/4]-1.In addition,we proof that- if G is a(n-1)-edge deletable BM-extendable,then g(G)=3.Where V(G)=2n,n≥2.There was a complete characterization for Harary graph H_m,v BM-extendable graphs in the hterature.Base on a complicated argument,we present a number of characterization for Harary graph H_m,v BM-extendable.Let G be a simple connected graph on 2n vertices with a perfect matching.For a positive integer k,1≤κ≤n-1,G is aκ-bipartite matching extendable if every bipartite matching of G with |M|≤κis included in a perfect matching of G,where 1≤κ≤n-1. We have the following conclusions:C_2n×P₂(n≥2) is 2-bipartite matching extendable. If G is 1-extendable,then G×P₂ is 2-bipartite matching extendable.If G is bipartite matching extendable,then G×P₂ is 2-bipartite matching extendable.