Some Results On Factors And Fractional Factors Of Graphs

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 operational research, chemistry, biology, network theory, information science, cybernetics, game theory, computer science and other disciplines. Graph theory is widely applied in branches of various disciplines, engineering and technology field and social sciences. As a sub field in combinatorial mathematics, graph theory has attracted much attention from all perspectives.Factor theory of graph 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., coding design, building blocks, the file transfer problems on computer networks, scheduling problems and so on, are related to the factors, factorizations and orthogonal factorizations of graphs [2]. The file transfer problem can be modelled as factors and (0, f)-factorizations (or f-colorings) of a graph. The design of Latin Squares and Room Squares are related to factors and orthogonal factorizations in 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 subset S of V(G), G-S denotes the induced subgraph of V(G)\S and G[S] denotes the induced subgraph of S. A vertex cut of 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 k(G) of G is the minimum k for which G has a k-vertex cut. G is said to be k-connected if k(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 kelements. The edge connectivity A(G) of G is the minimum k for which G has a fc-edge cut. G is said to be &-edge-connected if A(G) > k.Let g and / be two integer-valued functions such that 0 < g(x) < f(x) for all x € ViG). A ig, /)-factor F of (3 is a spanning subgraph of G such that gix) < dFix) < fix) for all x E ViG). If gix) = fix) for all x 0. // (a) f(X) = f(Y), g(X) = g(Y), (b) mk > k(G) > c(G[D}) +r + k, and (c) \D D E(x)\ < (m - 1)A; for all x G V(G) where E(x) is the set of edges incident with vertex x in G, then G has a (g, f)-factor excluding D.Theorem 2.1.5 Let G = (X,Y,E(G)) be a bipartite (mg,mf)-graph with edge-connectivity X(G) such that mk > X(G) > n and m>2 where g and f are two positiveinteger-valued functions defined on V(G) such that k < g(x) < f(x) for all x € V(G), f(X) = f(Y) and g(X) = g(Y). Then G has a (g, f)-factor excluding any given [^J edges .Set f{x) = g(x) for all x 6 V(G) in Theorem 2.1.4. We have the following result.Corollary 2.1.61? ^ei G be a bipartite mf-graph and let D be a set of edges such that \D\ = m+r, r > 0. If (a) k{G) > c(G[D])+r+k where k = min{/(x) : x e V{G)} and (6) dc_r)(x) > f(x) for all x 6 V(G), then G has an f-factor excluding D.Set f(x) = g(x) = 1 for all x € V{G) in Theorem 2.1.4 and Theorem 2.1.5, respectively. Then the following results are obtained.Corollary 2.1.7'^ Let G be a bipartite m-regular graph and let D be a set of edges such that \D\ = m + r, r > 0. If k(G) > c(G[D}) + r + k, 5{G - D) > 1, then G — D has a perfect matching.Corollary 2.1.8 Let G = (X,Y,E(G)) be a bipartite m-regular graph with edge-connectivity X(G)>n and m>2. Then G has a perfect matching excluding any given L^iiJ edges .Chvdtal [29] first introduced the definition of toughness, denoted byt(G) = min{ Jf[ : S C V(G),u,(G- S) > 2},where u(G — S) denotes the number of components of G — S and G is not complete graph. If G is complete, then t(G) = oo. Many authors investigated the relation of toughness and hamiltonicity or factor after Chvdtal's paper. G. Liu , Y. Ma [75] defined a parameter isolated toughness of a graphwhere i(G — S) denotes the number of isolated vertices of G — S and G is not complete graph. If G is complete, then I(G) = oo. Obviously I(G) > t{G). J. Qian in [86] gave a parameter in bipartite graph related to toughness.t\G) = min{ W :SCXovYMG-S)> 2},U\U — O)where G is not complete bipartite graph. Otherwise f(G) = oo. He studied the relationship between tf{G) and [a, 6]-factor or /-factor.We define a new isolated toughness in bipartite graphI'(G) = min{ J^js) : S C X or Y, i(G - S) > 2}where G is not complete bipartite graph. Otherwise I'(G) = oo. Obviously I'(G) > t'(G). We use this parameter to characterize (g, /)-factor in bipartite graph.Theorem 2.2.3. Let G = (X,Y,E(G)) be a bipartite graph and g, f be two positive integer-valued functions defined on V(G) such that a < g(x) < f(x) < b for all x e V{G), where a, b are integers and2 (<>+b-i)(a+b-2)-i ^ 5(G) > b and f(X) = /(Y), g{X) = g{Y). If I'(G) > 2±J=1, then G has a (g,f)-factor.Theorem 2.2.4 Let G = (X, Y, E(G)) be a bipartite graph and g,f be two positive integer-valued functions defined on V(G) such that a < g(x) < f(x) < b for all x G V(G), where a,b are integers and 1 < a < b. Let \X\ = \Y\ = n, f(X) = f(Y) and g(X) = g(Y). If I'(G) > 2^_a_b, then G has a (g, f)-factor .In Chapter 3 we pay our attention to the factors in ifiin-free graphs, where n > 3. ffi)n-free graphs are known to have many interesting properties. Here some sufficient conditions related to minimum degree are obtained for a Kin-free graph to contain an /-factor. We generalize the results in [31],[41] and [92]. Thus in the general case we get the sufficient condition for if1|n-free graph to have a (g, /)-factor.Theorem 3.1.1 Let a,b be non-negative integers and G be a connected K\>n-free graph. g(x), f(x) is the non-negative functions defined on V(G) such that 2 < n — 1 < o ^ - 4- -____-___I_________I- -____-—I----------1---------1 J~2+ 4a +4(n-l)+ 2a + 4a + 2 'then G has a (g, f)-factor.Let g(x) = f(x) in Theorem 3.1.1, we get the results in [41].Corollary 3.1.2'41' Let a, b be non-negative integers and G be a connected Ki>n-free graph. f(x) is the non-negative functions defined on V(G) such that 2 < n - 1 < a < f{x) < b and Y,xev(G) f(x) is even- tf a . (n ~ Vb , n ~then G has an f-factor.Set a = b = k, the following result in [31] holds.Corollary 3.1.3^*1 Let k>2 be an integer and G be a connected Kifn-free graph with k\V{G)\ even. If5{G) > ^^ + if + ^, then G has a k-factor.We also consider the degree condition to guarantee a /Ci>n-free graph to be an (/; m)-uniform graph. The results improve and generalize the results in [61] and [65].Theorem 3.2.4 Let a, b, n and m be positive integers with b>a>n + 2m = N. Let G be an (m + l)-edge-connected graph and f(x) be a non-negative integer-valued function defined on V(G) satisfying a < f(x) < b and YjX<=v{G) f(x) even- tf^ contains no Ki>n as an induced subgraph and>b . (JV1)& , a1 ANl)b Nl , -2 4(a-l) 4{N-l)+ 2(o-l) 4(a -1)then G is an (f;m)-uniform graph.Corollary 3.2.5 Let a, b, n and m be positive integers with b > a > n + 2. Let G be a 2-edge-connected graph and f(x) be a non-negative integer-valued function defined on V(G) satisfying a < f(x) < b and J2xev(G) f(x) even- tf @ contains no Ki>n as an induced subgraph and b4 (n ^then G is an f-uniform graph.In Chapter 4 we investigate (g, /)-factors and fractional (g, /)-factors in general graphs from different perspectives. Such as neighborhood condition, binding number and induced subgraph, etc. Some sufficient conditions related to these parameters for agraph to have a (g, /)-factor or a fractional (g, /)-factor are obtained and furthermore it is showed that the results are best possible in some sense.In recent years, more and more authors focused on the neighborhood conditions and factors. There are many results coming into being. Nissen[81] studied the relationship between neighbor unions and /c-factor. Matasuda[78] studied the neighborhood unions and [a, 6]-factors. We prove the following theorem for the existence of a (g, /)-factor, which is an extension of the theorems in [78, 81].Theorem 4.1.3 Let a and b be two positive integers and G be a graph of order n ^th n > (Q+bK2°+2fc-3) and 8 = 5{G) > kgte. Let g, f be two positive integer-valued functions defined on vertex set V(G) of G such that a < g(x) < f(x) < b. If \NG(x) U Nc{y)\ > ^ for any two non-adjacent vertices x and y of G, then G has a (9,!)- factor.We also give the binding number conditions to guarantee the existence of fractional (g, /)-factors in G. For a subset X of V(G), letNG(X) = |J NG(x). xexWe say that X is independent if NG{X) D X = 0. The binding number bind(G) is defined by Woodall[99]bind(G) = min{!M^|0 ^Xc V(G),NG(X)There are many known results on the binding number and factors (see [11, 32, 47, 99]). We obtain the following result about binding number and fractional (g, /)-factor.Theorem 4.2.5 Let a and b be two integers and G be a graph of order n with n > ^a+a' . Let g, f be two positive integer-valued functions defined on vertex set V(G) of G such that I < a < g{x) < f(x) < b and 2 < b. If bind{G) > {^$￡$ or 8(G) > ^jy, then G has a fractional (g, /)- factor.In the last of this chapter we consider the fractional (g, /)-factors and connected induced subgraphs. We obtain the following result.Theorem 4.3.4 Let G be a connected graph, andp be an integer such that 0 < p < \V(G)\. Let f be integer-valued function defined on V(G) such that 2 < f(x) < dG(x)for all x € V(G). Suppose that every connected induced subgraph H of order p of G has a fractional (g, f)-factor. Then G has a fractional (g, f)-factor.In Chapter 5, we focused on fractional matching extension and divided it into three sections. First we define the fractional defect-d matching of a graph. The necessary and sufficient conditions for a graph to have a fractional defect-d matching are given and the relation between the fractional defect-d matching and the toughness is discussed. Secondly, on the bases of fractional defect-d matching, we define the fractional (n, fc, d)-graph and discuss its properties and these properties are special for fractional factor. Finally, we study the fractional matching extension in K\ *&■, then G has a fractional defect-d matching.Let G be a graph and n, k, d be non-negative integers with n+3k+d < \V(G)\ — 2. Let G be a graph with a matching of size A;. For a matching M of size k of G, if there exists a fractional matching G^ containing M and h(e) = 1 for e € E(M), then G is called fractional ^-extendable. We also say that M can be extended to a fractional perfect matching of G. If deleting any n vertices of G the remaining subgraph G' has a fc-matching and every fc-matching can be extended to a fractional defect-d matching, then G is a fractional (n, k, d)-graph. In the following we always suppose that n, k, dsatisfy n + Zk + d < \V(G)\ - 2. At first we give a characterization of a fractional (n, k, d)-graph.Theorem 5.2.1 A graph G is a fractional (n, k,d)-graph if and only if the following conditions hold.(i) For any S C V{G) and \S\ > n, then i{G -S)<\S\-n + d. (ii) For any S C V(G) such that \S\ > n + 2k and G[S] contains a k-matching, then i(G - S) < \S\ - n - 2k + d.Theorem 5.2.4 Every fractional (n,k,d)-graph G is also a fractional (n',k',d)-graph, where 0 < n' < n, 0 < k' < k.We also investigate the effect on (n, k, d)-graph by deleting an edge. Theorem 5.2.7 If G is a fractional (n, k, d)-graph, then for any e G E(G), G — e is fractional (n — l,k,d+l) -graph.We have another property on fractional (n, k, d)-graph, when n = 0. It doesn't hold for re/0.Theorem 5.2.8 Graph G is a fractional (k,d)-graph if and only if for any matching M of size i, the graph G — V(M) is a fractional (k — i, d)-graph.In the third section of Chapter 5, we discuss the sufficient conditions related to connectivity for a /Clin-free graph to be fractional ^-extendable. Our results are as follows.Theorem 5.3.2 Let G be a (2k+ 2)-connected Kitk+3-free graph of odd order such that the set of the claw centers is independent. Then G is fractional k-extendable. When |V(G)| is even, the connectivity is (2k + 1) in Theorem 5.3.2. Corollary 5.3.3 Let G be a 2-connected claw-free graph of odd order. Then G has a fractional perfect matching.Corollary 5.3.4 Let G be a (2k + 2)-connected claw-free graph of odd order, then G is fractional k-extendable.In Chapter 6, we pay our attention to n-factor-critical graph and fractional n-factor-critical graph.At first, we impose on the fractional n-factor-critical graph and discuss its severalproperties.In [81] the maximal matching of a graph and the n-factor-critical graph are discussed. Here we consider the maximal matching of a graph and fractional n-factor-critical graph.Theorem 6.1.4 Let G be a connected graph and M be an arbitrary (fixed) maximal matching of G. IfG — V(e) is fractional n-factor-critical for every e € M, then G is fractional n-factor-critical.We also investigate the relationship between fractional factor-criticality and complete closures.Theorem 6.2.2 Let G be a graph of order p. Say V(G) = {xi,- ■ ? ,xp}. Then G is fractional n-factor -critical if and only if G'x. is fractional n-factor-critical for 1 < i < [|(p + n)"\, where G'x. is the graph obtained from G by local completion at Xj.Theorem 6.2.3 Let G be an (n + k)-connected graph. Let x E V{G) and a(G[Nc(x)}) < k with k>2 and let G' be the graph obtained from G by local completion atx. IfG' is fractional (n + k—1) -factor-critical, then G is fractional n-factor-critical.Theorem 6.2.4 Let s and k be integers with s > 3, k > 2. Let G be an (n+(s — l)k — l)-connected graph such that the centers of the induced K\tS in G are independent, let x be a vertex of G with ^(G[Nc(x)] < k and let G' be the graph obtained from G by local completion at x. If G' is fractional (n + (s — 2)k - 1)-factor-critical, then G is fractional n-factor-critical.A graph is said to be (a, b; n)-critical graph if after deleting any n vertices of G, the remaining graph has an [a, b]- factor. In [97] Teng Cong gave a sharp bound of the toughness of graph G to guarantee G to be (2, b; n)-critical graph. In this paper we investigate the sharp toughness and (a, b\ n)-critical graph and generalize the results in [97] and [105].Theorem 6.3.4 Let G be a graph, 2 < a < b, b > a(n + 1) and S(G) >a + n. If t{G) > a - 1 + ^(1 + n), then G is (a, b; n)-critical graph.We can easily define the fractional (o, b; n)-critical graph similar to (a, 6; n)-critical graph. The relation between fractional (o, b; n)-graphs and isolated toughness is ob-tained.Theorem 6.4.3 LetG be a graph, 1 < a < b, b > (a-l)(n+l) andS(G) > a+n. If I(G) >a— l + |(l + n), then G is a fractional (a, 6; n)-critical graph.