Factors And Fractional Factors Of Graphs

Since 1960s, graph theory has witnessed unprecedented development. It is of great advantage to apply graph theory in resolving problems in physics, chemistry, biology, network theory, psychology, computer science and other disciplines. The factor theory of graphs is an important branch in graph theory. It is a subject that receives most research in graph theory study. In our daily life many problems on optimization and network design, e.g., the file transfer problems on computer networks, scheduling problems and so on, are related to the factors, factorizations and orthogonal factorizations of graphs [1,6]. The file transfer problem can be modelled as factors and (0, f)-factorizations (or f-colorings) of a graph. In this thesis we pay our attention to factors, fractional factors and connected factors of graphs.All graphs considered are finite simple graphs. Let G be a graph with vertex set V(G) and edge set E(G). For a vertex v∈V(G), the degree ofÏ…in G is denoted by d_G(v). We write N_G(v) for the vertices adjacent to v in G, and N_G[v] for N_G(v)∪{v}. If S is a subset of V(G), for convenience we write d_G(S) instead of sum from v∈S d_G(v). If u∈V(G)\S, then we write e_G(u,S) to denote the number of edges joining u to a vertex in S. If T (?) V(G)\S, then we write e_G(T,S) instead of sum from u∈T e_G(u,S). For a subset S of V(G), G—S denotes the induced subgraph by V(G)\S and G[S] denotes the induced subgraph by S. A vertex cut of a connected graph G is a subset S of V(G) such that G—S is disconnected. A k-vertex cut is a vertex cut of k elements. The connectivityκ(G) of G is the minimum k for which G has a k-vertex cut. G is said to be k-connected ifκ(G)≥k. An edge cut of G is a subset of E(G) of the form [S, V(G)\S], where S is a nonempty subset of V(G). A k-edge cut is an edge cut of k elements. The edge connectivityλ(G) of G is the minimum k for which G has a k-edge cut. G is said to be k-edge-connected ifλ(G)≥k.Let g and f be two integer-valued functions defined on V(G) such that 0≤g(x)≤f(x) for all x∈V(G). A (g,f)-factor F of G is a spanning subgraph of G such that g(x)≤d_F(x)≤f(x) for all x∈V(G). If g(x) = f(x) for all x∈V(G), then a (g,f)-factor is called an f-factor. If f(x) =k for some nonnegative integer k and all x∈V(G), then an f-factor is called a k-factor. Especially, when g(x) = f(x) = 1 for every x∈V(G), a (g,f)-factor is called a 1-factor, i.e., a perfect matching. The definition of a perfect matching of G can also be seen in [6].The study on the factors of graphs started over one hundred years ago. In 1859, Reiss proved that the graph K_2n can be decomposed into 1-factors. In 1891, J. Peterson proved that every graph of even degree can be decomposed into the union of edge-disjoint 2-factors. He also showed that every 2-connected 3-regular graph has a 1-factor. These two results can be viewed as a forerunner of modern graph factor theory. In 1947 Tutte[90] gave a criterion for the existence of 1-factors of a graph. This elegant theorem is perhaps the most fundamental result in factor theory. In 1952 Tutte[91] again gave a criterion for a graph to have a f-factor. Lovász[65] obtained a necessary and sufficient condition for a graph to have a (g,f)-factor. Since then numerous results on factor theory sprung forth.A fractional (g,f)-indicator function is a function h that assigns to each edge of a graph G a number h(e) in [0,1] so that for each vertex x we have g(x)≤d_Gh(x)≤f(x), where d_Gh(x) = sum from e∈E_x h(e) is the fractional degree of x in G with E_x = {e:e = xy∈E(G)}. let h be a fractional (g,f)- indicator function of G. Let E_h = {e:e∈E(G) and h(e) 0}. If G_h is a spanning subgraph of G such that E(G_h) = E_h , then G_h is called a fractional (g,f)-factor of G. When g(x) = f(x) for every x∈V(G), a fractional (g,f)-indicator function is called a fractional f-indicator function. Let h be a fractional f-indicator function of a graph G. Set E_h = {e:e∈E(G) and h(e)≠0}. If G_h is a spanning subgraph of G such that E(G_h) = E_h, then G_h is called a fractional f-factor of G.Fractional graph theory is a relatively younger branch. The first article on this topic was written by Claude Berge in his Fractional Graph Theory in 1978 [4]. In 1997 E. R. Scheinerman and D. H. Ullman wrote a new book[85] concerning fractional graph theory which covered nearly all the main topics such as fractional matching, fractional edge coloring, fractional coloring, fractional arboricity and fractional isomorphism. Nearly every integer-valued invariant encountered in a first course in graph theory gives to a fractional analogue.Connected factor theory was initiated by Kano, who proposed some problems and conjectures in 1993, concerning the existence of connected factors in graphs[35]. Kano's problems and conjectures promoted the research of connected factor in the past ten years. Various results of connected factors related to degree conditions,. connectivity conditions, binding number conditions et al. are obtained.This thesis is divided into five chapters. We mainly discuss four problems. (1) The existence of (g,f)-factors in graphs; (2) Some results on uniform graphs; (3) Fractional (g,f)-factors of graphs; (4)Some results on connected factors of graphs.In Chapter 1, we give a concise survey on factors, fractional factors and connected factors.In Chapter 2, we investigate the conditions which guarantee the existence of (g,f)-factors in K_1,n-free graphs and in general graphs. This chapter is divided into two parts. One part is to discuss the conditions related to the stability number which guarantee the existence of factors in K_1,n-free graphs and in general graphs. It is shown that some results is best possible in some sense. The other is to investigate relationship between the binding number and the existence of Hamilton (g,f)-factors in graphs.Theorem 2.1.6 Let G be a connected K_1,n-free graph and let f be a nonnegative integer-valued function defined on V(G) such that 1≤n－1≤a≤f(x)≤b for every x∈V(G). If f(V(G)) is even,δ(G)≥b+n－1, andα(G)≤4a(δ－b－n+1)/(b+1)²(n－1), then G has an f-factor.The following result shows that the stability number and minimum degree condition for the existence of connected (f－2,f)-factors.Theorem 2.1.7 Let G be a connected K_1,n-free graph with |V(G)|≥3 and let f be a nonnegative integer-valued function defined on V(G) such that 1≤n－1≤a≤f(x)－2≤b for every x∈V(G). If f(V(G)) is even,δ(G)≥b+ n－1, andα(G)≤min{κ(G),4a(δ－b－n+1)/(b+1)²(n－1)}, then G has a connected (f－2,f)-factor. Then we try to show that the similar results hold in general graphs, and we obtain the following results.Theorem 2.1.9 Let G be a connected graph of order n and let f be a nonnegative integer-valued function defined on V(G) such that 1≤a≤f(x)≤b for every x∈V(G). Where n≥(a + b). If f(V(G)) is even, 6(G)≥bn/(a + b), andα(G)≤4a(δ－b)/(b+1)², then G has an f-factor.Theorem 2.1.10 Let G be a connected graph of order n≥3 and let f be a nonnegative integer-valued function defined on V(G) such that 1≤a≤f(x)－2≤b for every x∈V(G), where n≥(a + b). If f(V(G)) is even, 6(G)≥bn/(a + b), andα(G)≤4a(δ－b)/(b+1)², then G has a connected (f－2,f)-factor.We also obtain the following result.Theorem 2.1.11 Let G be a connected graph of order n and let f be a nonnegative integer-valued function defined on V(G) such that 1≤a≤f(x)≤b for every x∈V(G), where n≥(a + b). If f(V(G)) is even, S(G)≥bn/(a + b), andα(G)≤4a(δ－b)/(b+1)², then G has a connected (f,f+1)-factor.If n = a + b, we get the following Corollary.Corollary 2.1.1 Let G be a connected graph of order n and let f be s nonnegative integer-valued function defined on V(G) such that 1≤a≤f(x)≤b for every x∈V(G), where n = a + b. If f(V(G)) is even, 6(G)≥b andα(G)≤4a(δ－b)/(b+1)², then G has an f-factor.The binding number of G is defined by Woodal,Many authors investigated the relationship between binding number and the existence of factors. In section 2, we show the relationship between the binding number and the existence of Hamilton (g,f)-factor in graph G.Theorem 2.2.4 Let G be a connected graph of order n, a and b be integers such that 4≤a≤b. Let g and f be positive integer-valued functions defined on V(G) such that a≤g(x) < f(x)≤b for every x∈V(G). Suppose that n≥(a+b－5)²/(a－2). If bind(G)≥(a+b－5)(n－1)/((a－2)n－3(a+b－5)), and for any nonempty independent subset X of V(G), |N_G(X)|≥((b－3)n+(2a+2b－9)|X|)/(a+b－5), Then G has a Hamilton (g,f)-factor. In Chapter 3 we pay our attention to the conditions which guarantee the existence of (g,f)-factors, f-factors and k-factors with prescribed properties. We consider three aspects of this topic in this chapter. In the first section, we investigate the existence of k-uniform graphs, which extend the result in[12]; Some conclusions concerning the relationship between (m,n)-graphs and (g,f)-uniform graphs are obtained in the second section; In the last section, we give some results on the existence of f-uniform graphs.Theorem 3.1.3 Let k≥2 be a positive integer and G be a graph of order n≥4k+8 withδ(G) > k + 1 and kn even. Suppose that max{d_G(x),d_G(y)}>n/2 for any nonadjacent vertices x and y of V(G). Then G is a k-uniform graph.Concerning the existence of (g,f)-factors with prescribed properties, we obtain the following results.Theorem 3.2.4 Let G be a graph, g and f be two integer-valued functions defined on V(G) such that 0≤g(x) < f(x) for every x∈V(G). Let m≥2 be integer. Then if one of the following two conditions is satisfied,(1) G is a (mg, mf－m+1)-graph and g(x) is even for every x∈V(G);(2) G is a (mg+m－1,mf)-graph and f(x) is even for every x∈V(G), then G is a (g,f) -uniform graph.Theorem 3.2.5 Let G be a connected graph, g and f be two positive integer-valued functions defined on V(G) such that g(x)≤f(x) for every x∈V(G). Let m≥2 be integer. Then (mg+1,mf)-graphs and (mg,mf－1)-graphs are (g,f)-uniform graphs.If g and f are constricted, we have the following stronger result.Theorem 3.2.6 Let G be a graph, g and f be two even integer-valued functions defined on V(G) such that 0≤g(x) < f(x) for every x∈V(G). Let m≥2 be integer. If G is a (mg,mf)-graph, then G is a (g,f)-uniform graph.Theorem 3.3.2 Let G be a 2-edge-connected graph, f be an integer-valued function defined on V(G) such that f(x)≥2 for every x∈V(G). |V(G)|≥max_x∈V(G)f(x)+3. Ifδ_G(S,T) = d_G－S(T)－f(T)－h_G(S,T)+f(S)≥2 (?) f(x) for any disjoint S,T (?) V(G) such that |S |≥2, then G is an f-uniform graph.When f(x) = k for every x∈V(G), the result in [56] is the following Corollary of Theorem 3.3.2.Corollary 3.3.3 Let G be a 2-edge-connected graph. |V(G)|≥k+3. Let k≥2 be an integer. Ifδ_G(S,T) = d_G－S(T)－k|T|－h_G(S,T)+k|S|≥2k, for any two disjoint subsets S and T of V(G) with |S|≥2. Then G is a k-uniform graph.In Chapter 4 we focus on fractional (g,f)-factors and divided Chapter 4 into two sections. First we investigate the stability number condition and the existence of fractional f-factors in graphs, which shows that the fractional analogue of Conjecture 2.2.8 is true. Furthermore, it is showed that the result is best possible in some sense. Second, we discuss various conditions for the existence of fractional uniform graphs.Theorem 4.1.4 Let G be a connected graph and let f be a nonnegative integer-valued function defined on V(G) such that 0≤a≤f(x)≤b for every x∈V(G). If S(G)≥b, andα{G) <(4a(δ－b))/(b+1)², then G has an fractional f-factor.In section 2, we focus on the existence of fractional (g,f)-factor with prescribed properties.Theorem 4.2.1 Let k≥2 be an integer and G be a connected graph of order n≥k + 1. Ifφ(S,T₁) = k|S|－k|T₁|+d_G－S(T₁)≥2k－1 for any two disjoint subsets S and T₁ of V(G) with |S|≥2, then G is an fractional k-uniform graph.Theorem 4.2.2 Let k be a positive integer and G be a graph of order n≥k + 2. If for any S (?) V(G) with |S|≥1, where p_j(G－S) denotes the number of vertices with degree j in G—S, then G is an fractional k-uniform graph.When k = 1, we have the following necessary and sufficient condition for a graph to be an fractional 1-uniform graph. Theorem 4.2.3 Let G be a connected graph. Then G is an fractional 1-uniform graph if and only if i(G－S)≤|S|－2 when S is not independent; i(G－S)≤|S|, when S is independent, where i(G—S) denotes the number of isolated vertices of G－S.Based on Theorem 4.2.3, we can obtain the following result.Corollary 4.2.4 Let G be a connected graph of order n≥4. If i(G－S)≤|S|－2 for any S (?) V(G), then G is an fractional l-uniform graph.In Chapter 5, we deal with connected factors in graphs. As well known, the connected factor problem is a NP-complete problem. Here some sufficient conditions related to minimum degree, binding number, and stability number for graphs to have connected (g,f)-factors and Hamilton (g,f)-factors are given.Theorem 5.1.4 Let G be a connected graph of order n, and a, b two integers such that 2≤a≤b. Let g, f be two integer-valued functions defined on V(G) such that a≤g(x)≤f(x)≤b for every x∈V(G) and f(V(G)) is even. If n≥(a+b)²/a, bind(G)>((a+b)(n－1))/an, then G has a connected (g,f+1)-factor.Theorem 5.1.5 Let G be a connected graph of order n, a and b be integers such that 3≤a≤b and b≥4. Let g, f be positive integer-valued functions defined on V(G) such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose that n≥(a+b－4)²/(a－2) and f(V(G)) is even. If bind(G)>(a+b－4)(n－1)/((a－2)n－5/2(a+b－4)) and for any independent set X C V(G), N_G(X)≥((b－3)+(2a+2b－9)|X|)/(a+b－5), then G has a Hamilton (g,f)-factor.Theorem 5.2.2 Let G be a 2-connected graph of order n and let k≥2 be a positive integer such that n≥3k－1 and kn is even. Ifα(G)≤4k(δ－k)/(k+1)²,δ(G)≥(n+1)/3, and for each pair of nonadjacent vertices u,v in G max{d(u),d(v)}≥(n－k)/2.Then G has a connected [k,k+1]-factor.