The Factors In Bipartite Graphs

The factor problem is one of popular problems in graph theory because of itsimportant meaning. Unitl now, there have been rather abundunt results. The researchon fractional factor is also a new problem which has been put forward. In the following,we will introduce some conceptions such as factor, fractional factor. Let g and f betwo integer-valued functions defined on V(G), such as g＜f for every x∈V(G), suchthat 0≤g(x)≤f(x), for every x∈V(G). A (g, f)-factor of G is a spanning subgraphF of G, such that g(x)≤d_F(x)≤f(x) for every x∈V(G). Let g(x)=a, f(x)=b,the factor above is called a [a, b]-factor. Let a=b=k, the [a, b]-factor is called ak-factor.Let h is a function defined on the edge set E(G) and for every e∈E(G), h(e)∈[0,1]. Let d_G^h(x)=∑_e∈Ex h(e), and E_x={e|e=xy∈E(G)}, we call d_G^h(x) asfractional degree of x in G. If h satisfies g(x)≤d_G^h(x)≤f(x) for x∈V(G), h iscalled a fractional (g,f) denoted function of G. Let E_h ={e∈E(G)|h(e)≠0},E_h= E(G_h), if G_h is a spanning graph of G, then G_h is called a fractional (g, f)-factor.Fractonal k-factor can be defined in the same way. Some terminology, notationin thethesis are given in chapter 1. In chapter 2, a necessary and sufficent condition forthe fractonal k-factor in the bipartite graphs is introduced. In chapter 3, we give aproof on bipartite graphs containing cycles and matchings. In chapter 4, we studythe relationship between a new parameter related to toughness and the existence offactors.We give the main results as follows:Theorem 2.1 Let G = (X, Y; E) is a bipartite graph, G has a fractional k-factorif and only if for every S(?)X, T(?)Y sum from j=0 to (k-1)(k-j)P_j(G-S)≤k|S|,and sum from j=0 to (k-1)(k-j)P_j(G-T)≤k|T|.for every S(?)X,T(?)Y. P_j(G)=|{x|d_G(x)=j}|. Theorem 2.2 Let G = (X, Y; E) is a bipartite graph , a, b are two positiveinteger, and a≤b ,if sum from j=0 to (a-1)(a-j)|(G-S)_j∩T|≤b|S|,and sum from j=0 to (a-1)(a-j)|(G-T)_j∩S|≤b|T|,for every S(?)X, T(?)Y, then G has a [a, b]-factor. G_i ={x|d_G(x)=i}.Theorem 3.1 Let G = (V₁, V₂; E) is a bipartite graph, |V₁|=|V₂|=n≥5, andδ(G)≥[1/2n]+1. For l is an any positive integer which satisfies(1) 3≤l≤n-1(2) l≠n(mod2),then there are a cycle whose length is 2l and a matching which contains n-l edges,and V(C)∩V(M)=φ.Generally speaking, N_G(x) denotes neighboring set of x in G.Let N(x,T) =N_G(x)∩T denotes neighboring set of x in T and d(x, T) =|N(x, T)|.Theorem 4.2 Let G = (X, Y; E) is a bipartite graph, if any set T(?)XorY,r₁≤2,且t'(G)=1,then there is a 2-factor in bipartite graph G. r₁=|R₁|,R₁={x|d(x,T)=1,x∈N(T)}.