Scores Of Factor Critical Graphs And Related Properties

All graphs considered in this thesis will be simple undirected.Let G=(V(G),E(G))be a graph,where V(G)and E(G)denote the vertex set and edge set of G,respectively.We use d_G(x) to denote the degree of x in G andδ(G)to denote the minimum vertexdegree of G.For any S (?)V(G),the subgraph of G induced by S is denoted by G[S],we write G-S for G[V(G)\S].For any S(?)V(G),we use o(G-S)and i(G-S)to denotethe number of odd components and isolated vertices in G-S.Let g(x)≤f(x)be two nonnegative integral-valued functions defined on V(G)and let H be a spanning subgraph of G.We call H a (g,f)-factor of G if g(x)≤d_H(x)≤f(x)holds for each x∈V(G).Similarly,H is an f-facor(or g-factor)of G if g(x)=f(x)for each x∈V(G).If g(x)=a,f(x)=b for each x∈V(G)and a,b are two positivesintegers,then a (g,f)-factor is called an [a,b]-factor.In particular,when g(x)= f(x)=1holds for each x∈V(G),the (g,f)-factor becomes 1-facor which is also called perfectmatching.Let g(x)≤f(x)be two nonnegative integral-valued functions defined on V(G)andlet h(e)∈[0,1] be a function defined on E(G).Let d_G^h(x)=∑_e∈Exh(e),where E_x={xy:xy∈E(G)}.Then d_G^h(x) is called the fractional degree of x in G.We call h an indictorfunction if g(x)≤d_G^h(x)≤f(x)holds for each x∈V(G).let E^h={e:e∈E(G),h(e)≠0} and G_h be a spanning subgraph of G such that E(G_h)=E^h.We call G_h a fractional-(g,f)-factor.Similarly,we can define the fractional-k-factor,fractional-[a,b]-factor of G.In particular,when g(x)=f(x)=1 holds for each x∈V(G),fractional-(g,f)-factorbecomes fractional-1-factor which is also called fractional perfect matching.The problem of factors in graphs is one of the main problems in the research of graph theory.The study on the factors of graphs started over hundred years ago,but untill the1970s did it become propular.So far,many results on the existence of factors in graphshave been gained.Fractional graph theory is a relatively younger branch,so there stilllots of problems need to be solved.This thesis is divided into six chapters.The fourth and fifth chapter are the maincontents of this thesis,in the two chapters,we obtain some results about fractional-factor-critical graphs and fractional-factor-extendable graphs.The first chapter is the basis of this thesis.We first introduce some concepts,terms and signs which are referred,and then review the history of the graph theory and factors in graphs.In the end we give some usefull and important parameters which are oftenused in dealing with problem of factors in graphs.In the second chapter,both for the integral factors and fractional factors,we summarizethe main results about the existence of them which have been concluded.In the third chapter,by analysis we obtain two effective methods to solve the existence of factors in graphs.In the fourth chapter,we mainly study some properties of the fractional-factor-criticalgraphs (for positive integers r and n,a graph G is said to be fractional-(r,n)-factor-criticalif G-T has a fractional-r-factor for any n-subset T of V(G)) and obtain the following results:■Let G be graph withδ(G)≥r+n and the isolate toughness I(G)≥r+n-1/r. Then G is a fractional-(r,n)-factor-critical graph.■Let G be graph withδ(G)≥r+n.If G is a fractional-(r,n)-factor-critical graph,then G is a fractional-(r,n-1)-factor-critical graph as well.■If G-{v} has fractional-r-factors for any v∈V(G).Then G has fractional-r-factors as well.In the fifth chapter,we mainly study some properties of the fractional-(r,k)-extendablegraphs (for positive integers r and k,G is said to be fractional-(r,k)-extendable if G-Tadmits an fractional-k-extendable for any r-subset T of V(G))and get the following results:■A graph G is fractional-(r,k)-extendable if and only if i(G-U)≤|U|-2k-rholds for any U(?)V(G)with |U|≥2k+r and G[U] contains a k-matching.■Every fractional-(r,k)-extendable graph is also a fractional-(r',k')-extendable graph where 0≤r'≤r,0≤k'≤k.■Let G be a graph.Then G is fractional-(r,k)-extendable if and only if for anyi-matching M of G,1≤i≤k,G-V(M)is fractional-(r,k-i)-extendable.■A fractional-(r,k)-extendable graph is fractional-(k+[r/2])-extendable.In the sixth chapter,we summarize the mian contents of the thesis and provide someproblems for future study.