| Since 1960s, graph theory has become one of the subfields in mathematics that develop fastest. It is of great advantage to apply graph theory in resolving problems in physics, chemistry, computer science and other disciplines. Factor theory is one of the main problems in Graph Theory.All graphs considered are finite simple graphs. Let G= G(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For a vertex v of G, we denote the degree of v by dG(v) and the neighborhood of v by NG(v). For any subset we denote the neighborhood of X by and the induced subgraph of The number of components of G-X and the number of odd components of G-X are denoted by c(G-X) and o(G-X) respectively. We denote the minimum and maximum vertex degree of G byδ(G) and△(G) respectively.Let g and f be two nonnegative integer-valued functions defined on V(G). A spanning subgraph F of G is called a (g.f)-factor if it satisfies g(x)≤for every then F is called a (1,f)-factor. If for every then a (g,f)-factor is called a [a,b]-factor. If for every v∈V(G). dF(v)= f(v), then F is a f-factor of G. If dF(v)= k, then F is called a k-factor. Let G be a graph,f:V(G)→{1,3,5,...}, if H is a subgraph of G such that dH(x)∈{1,3,5,...,f(x)}, then H is a (1,f)-odd subgraph of G. if H is a spanning subgraph of G, then H is a (1,f)-odd factor of G.For any [0.1] be a function defined on E(G). For any vertex v, let then we call as the fractional degree of v in G. We call h a fractional (g,f)-indicator function if holds for any Let and Gh be a spanning subgraph of G such that E(Gh)= Eh, we call Gh a fractional (g,f)-factor of G, h is the indicator function of Gh.Let g(x)≡1, then Gh is a fractional (1,f)-factor of G. Particularly, if f is an odd, integer-valued positive function defined on V(G), and for any let g(x)= 1, then Gh is a fractional (1,f)-odd factor of G. For any then a fractional (1,f)-odd factor is called fractional{1,3,5,...,2n-1}-factor. Similarly, we can define the fractional f-factor, fractional k-factor, etc.A matching M of G is the independent edge sets of G, if M is a spanning subgraph of G, then M is called a perfect matching of G. A perfect matching is also called a 1-factor of G. Let G be a graph with order p. p is even and n is a positive integer, p≥2n+2. A graph G is n-extendability if any matching of n edges (called n-matching) can be extended to a perfect matching of G.Yinghong Ma and Guizhen Liu gave the definition of fractional n-extendable, studied the proposition of it and gave some results. A graph is called fractional n-extendable if G has a n-matching and for any k-matching M of G, there ex-ists a fractional 1-factor Gh of G such that for any e∈M, h(e)=1. Similarly, a graph is called fractional (1,f)-extendable if G has a n-matching and for any k-matching M of G, there exists a fractional (1,f)-factor Gh of G such that for any we also called that G has a n-extendable fractional (1,f)-factor.In 1980, Plummer gave a series of propositions about n-extendable graphs, from then on, many researchers have studied n-extendable graph theory. Frac-tional (1,f)-factor is a new problem which was proposed in recent years, the results about (1,f)-factor obtained now are much less than that of other types of factors. In the thesis, we give some new results about fractional (1,f)-factor.For convenience, for any function f defined on V(G), we denote f(S)= We call a matching with d edges as a d-matching and we denote the number of edges of the maximum matching of G[S] by ind(S).In this thesis, we focus on fractional (1,f)-factor. There are four chapters in the thesis. In Chapter 1, we introduce some basic notations of graphs and give the background and new results about factors and fractional factors of graphs. In Chapter 2, we discuss about fractional(1,f)-factor, here are our main results:Theorem 2.1.4 Let G be a graph. Then G has fractional (1,f)-factor if and only if for any subset S of V(G), i(G-S)≤f(S) holds, where i(G-S) denotes the number of isolated vertices of G-S.Theorem 2.1.5 Let G be a graph. If G has a fractional (1,f)-factor, then there exists a fractional (1,f)-factor Gh,, for anyTheorem 2.2.9 Let G be a graph and f:V(G)→Z+. Then G has a n-extendable fractional (1,f)-factor if and only if for any where D is a d-matching of G and d=min{ind(S),n}.Theorem 2.3.1 Let G be a graph and f:V(G)→Z+. Then G has a fractional (1,f)-factor by deleting any n vertices if and only if for any S (?)In Chapter 3, we discuss about fractional (1,f)-odd factor of graphs in cases of G are special and general. Our main results are: Theorem 3.2.2 Let G be a connected graph and f:V(G)→Z+. If G has a fractional (1,f)-odd factor, then for any S(?)V(G), we have i(G-S)≤f(S), but the reverse does not hold.In Chapter 4, we discuss about the relationship between toughness and fractional (1,f)-factor, here is our main result: Theorem 4.1.6 Let G be a graph, b be a positive integer and b> max{1, n},δ(G)> n+2. If then G is a (1,6, n)-extendable graph. |
PDF Full Text Request