The Study On Graph Factors And Related Problems

Graph theory is of great importance among branches of discrete mathematics,which is more and more widely applied in many fields.For instance,extremal graph theory,hypergraph theory,complex network,algorithmic graph theory,fuzzy graph the?ory and so on.The theory of graph factors is one of the active issues in graph theory,which has recently gained more and more attention.And graph factor has a wide range of applications in computing science,network design,coding design and so on.This paper concentrates on discussing the relationship between graph factors and graphic parameters and gives sufficient conditions for the existence of graph factors.Just because graphic parameters reflect the structures and properties of graphs from a different perspective,we specifically focus on charactering the existance of fractional critical graphs and fractional covered graphs by using parameters such as toughness,binding number,connectivity,minimum degree and neighborhood union.This thesis is organized as follows:In Chapter 1,we introduce the backgrounds and purposes of factor theory in Sec-tion 1.1.Then we review the research history and outline the latest development of re-lated fields such as connected factors,parity factors,fractional factors and hypergraph matchings in Section 1.2.Finally,we give the main results in this paper in Section 1.3.In Chapter 2,we summarize some concepts and symbols frequently used in graph theory.Then we describe some commonly used parameters,for example,toughness,binding number,neighborhood union and some others.In Chapter 3,by using toughness and connectivity condition,we study all fractional(a,b,k)-critical graphs and get the following results.· We give a sufficient condition for all fractional(a,b,k)-critical graphs by tough-ness and obtain that if ?(G)?(b2-1)+ak/a,then G is all fractional(a,b,k)-critical;at the end of this section we analyze that the bound is tight(Section 3.2).· By using the connectivity condition,we give the existance of all fractional(a,b,k)-critical graphs and prove that if K(G)?max?(b+1)2+2k/2,(b+1)2?(G)+4ak/4a?.then G is all fractional(a,b,k)-critical.Furthermore,we show that this bound is tight(SectionIn Chapter 4,we study the existance of fractional ID-[a,b]-critical graphs subject to certain conditions.The main result is as follows:If ING(x1)?NG(X2)?…?NG(Xr)|?(a+b)n/a+2b for any independent subset ?x1,x2,…,Xr?in G,then G is fractional ID-[a,b]-factor-critical.Furthermore,we prove the bound is tight.This result generalizes the known result obtained by Zhou,Yang and Sun[Discuss.Math.Graph Theory,2016,36(2):409-418].In other words,if NG(x)U NG(y)|?(a+b)n/a+2b for any two nonadjacent vertices x,y V(G),then G is fractional ID-[a,b]-factor-critical(Section 4.3).In Chapter 5,we use degree condition,neighborhood union and binding number to prove the existance of fractional covered graphs.The key results are as follows:· We use degree condition to get a sufficient condition for fractional[a,b]-covered graphs and obtain that if G satisfies max ?dG(x),dG(y)??a(n+1)/a+b for each pair of nonadjacent vertices x,y of G,then G is a fractional[a,b]-covered graph,which is more general than the result[Ars Comb.,2015,118:135-142]that if max{dG(x),dG(y)}?(n+1)/2 for each pair of nonadjacent vertices x,y of G,then G is a fractional k-covered graph.At the end of this section we prove that our bound is best possible(Section 5.2).· We use neighborhood union condition to get a sufficient condition for fractional[a,b]-covered graphs,that is to say,for any given integer r?2,if G satisfies|NG(x1)?NG(x2)?…?NG(xr)|?a(n+1)/a+b for any independent subset ?x1,x2,…,xr?of G,then G is a fractional[a,b]-covered graph.When a = b = k and r = 2,as a corollary of our main result,we derive the result in[Ars Comb.,2015,118:135-142].Also,we show that the bound a(n+1)/a+b is tight(Section 5.3).· By binding number condition,we obtain a sufficient condition for fractional k-covered graphs and prove that if bind(G)>(2k-1)(n-1)/kn-2k.then G is fractional k-covered.Finally,we prove the bound is best possible(Section 5.4).In Chapter 6,we consider randomly orthogonal factorizations in a bipartite(0,mf m+1)-graph G and give the sufficient condition of G having a(0,f)-factorization ran-domly r-orthogonal to arbitrarily given mr-subgraphs.In Chapter 7,we summarize this dissertation and give several problems for further research.