|
The factor problem is one of popular problems in graph theory because it is playing an increasing important role in the many areas. The theory about 2-factor of graphs has been used widely in the practical problems as traffic, computer networks and so on. Until now, there have been rather abundant results. The research on fractional factor has been put forward. Some conceptions such as factor, fractional factor have been given by scholars.In this paper, we study 2-factor in balanced bipartite graphs, and several constraints for the existence of 2-factor has been given. The contents of this paper consist of five chapters.The first chapter expounds some basic results and the situation of study of graph theory and factor theory, in particular the 2-factor.We considered the existence of 2-factor in balanced bipartite graphs in the second chapter. And we found several constraints for the existence of 2-factor in balanced bipartite graphs. The third chapter we study the relationship between a new parameter related to toughness and the existence of 2-factor.In the fourth chapter, a necessary and sufficient condition for the fractional 2-factor in balanced bipartite graphs is introduced.The last chapter discusses the summary of this paper.We obtain the main results as follows:Lemma 2.2.6 Let G be a balanced bipartite graph of order 2n, n> 4 and M is a perfect matching of G, then G contains two vertex-disjoint M-cycles C1, C2.Theorem 2.2.7 Let G be a balanced bipartite graph of order 2n, n>4k-4 where k≥2 is a integer, and then give any perfect matching M of G, G contains a M-2-factor with exactly k components.Lemma 2.2.8 Let G=(X,Y) be a balanced bipartite graph of order 2n,let s≥3, and If G contains k cycles with vertex-disjoint of length at least 2s, then contains a Hamilton-Path. Theorem 2.2.9 Let G=(X,Y) be a balanced bipartite graph of order 2n, let s>2,and n≥sk,If G contains k cycles with vertex-disjoint of length at least 2s, then G contains a 2-factor with at least k cycles of length at least 2s.Lemma 3.2.1 Let G=(X,Y) be a bipartite graph, t’(G)≤1.Theorem 3.2.2 Let G= (X,Y) be a balanced bipartite graph of order 2n and G is connected. If then G contains a 1-factor.Theorem 3.2.3 Let G= (X,Y) be a balanced bipartite graph, if any set T c:X or Y, r1≤2 and t’(G)=1, then G contains a 2-factor. r1=|R1|, R1={x|d(x,T)=1,x∈N(T)}.Theorem 4.2.1 Let G= (X,Y) be a balanced bipartite graph, G has a fractional 2-factor if and only if for every S(?)X, T(?)Y, andTheorem 4.2.2 Let G=(X,Y) be a balanced bipartite graph, a, b are two positive integer, and a≤b. If for every S(?)X,T(?)Y, and Then G contains a [a, b]-factor.
|