Factors And Fractional Fractors Of Graphs

Along with the appearance of huge electronic computers and rapid devel-opment of computer science, especially the appearance and development of the computer network, graph theory has great development and prosperity.It is of great advantage to apply graph theory in resolving problems in op-erations research, physics, chemistry, biology, network theory, information sci-ence, cybernetics, game theory, computer science and other disciplines. So s-tudying problems in graph theory is very important both in theory and in reality.Factor theory is one of the main problems in Graph Theory, which re-ceives most research in the graph theory study. However, it became popular until1970s. Thus far, a number of results that relate to the existance of factors and fractional factors in graphs have come out.This thesis is divided into four chapters. We largely discuss problems as follows.In Chapter1, we introduce some basic concepts and summarize the main results about the existance of factors and fractional factors.In Chapter2, we investigate the toughness conditions which guarantee the existence of fractional ID-κ-factor-critical graph.Let G be a graph of order n, where n≥k+2, δ(G)> k+n/4k, and k≥2is an integer. If t{G)≥k2+6k, then G is fractional ID-κ-factor-critical.In Chapter3, we pay our attention to the independent number and degree conditions, which guarantee the existence of fractional ID-[a,b]-factor-critical graph and (g,f)-factor. In the first section, we study the relationship between the independent number and degree conditions and the existence of fractional ID-[a,b]-factor-critical graph. In the last section, we show the conditions which guarantee the existence of (g,f)-factors in general graphs. Let G be a graph,and a and b two integers with1≤a≤b.If α(G)≤4b(δ(G)-b+1/(a+1)2+4b,then G is fractional ID-[a,b]-factor-critical.Let a and b be two positive integers and G a graph of order n with n≥2(a+b)(a+b-1)/a,Let g,f be two positive integer-valued functions defined on V(G) with a≤g(x)<f(x)≤b.If δ(G)≥b/a+(a+b-1)2/4a and max{dG(x),dG(y)}≥bn/a+b for any two nonadjacent vertices x and y in G,then G has a(g,f)-factor.In Chapter4, we give a neighbourhood condition for graphs to be fractional ID-[a,b]-factor-critical.Let a and b be two integers with2≤a≤b,and let G be a graph of order n with n>1+(a+2b-1)(2a+b-4)/b.Suppose that for any subset X (?) V(G),we haveThen G is fractional ID-[a,b]-factor-critical.