Factors And Fractional Factors Of Graphs

Graphs are very powerful tools for creating mathematical models of a wide variety of situations. The study of graph theory started over two hundreds years ago. The earliest known paper is due to Euler (1736) about the seven bridges of Konigsberg. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. Graph theory is widely applied in branches of various disciplines, engineering and technology field and social sciences. It is of great advantage to apply graph theory in resolving problems in operational research, physics, chemistry, biology, network theory, information science, cybernetics, game theory, computer science and other disciplines. Graph theory has become one of the subfields in mathematics that develop fastest. As a subfield in combinatorial mathematics, graph theory has attracted much attention from all perspectives.The factor theory of graphs is an important branch in the graph theory. It is a subject that receives most research in the 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 [1]. 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. In this thesis we pay our attention to factors, fractional factors and their related properties. 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. 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. 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κ(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.Let g and f be two integer-valued functions 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)≤dF(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 [17].The study on the factors of graphs started over one hundred years ago. In 1859, Reiss proved that the graph K2n 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. To extend matching theory from bipartite graphs to general graphs (i.e. non-bipartite graphs), In 1947 Tutte [85] 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 [86] again gave a criterion for a graph to have a f-factor. Lovasz[68] 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 graph G a number in [0,1] such that for each vertex x∈V(G) we have g(x)≤dGh(x)≤f(x), where is the fractional degree of x∈V(G) with Let h be a fractional (g,f)-indicator function of a graph G. Set If Gh is a spanning subgraph of G such that E(Gh)=Eh, then Gh is called a fractional (g,f)-factor of G. When g(x)=0 and f(x)=1 for all x∈V(G), a fractional indicator function is an indicator function of a fractional matching. If g(x)= f(x)=k, then a fractional (g,f)-factor is called a fractional k-factor. When g(x)=f(x)=1 for every x∈V(G), a fractional (g,f)-indicator function is an indicator function of a fractional perfect matching, that is, a fractional 1-factor.The fractional graph theory is a relatively younger branch. The first mono-graph on this topic was written by Claude Berge in his Fractional Graph Theory in 1978 [14]. In 1997 E. R. Scheinerman and D. H. Ullman wrote a new book con-cerning fractional graph theory which covered nearly all the main topics such as fractional matching, fractional edge coloring, fractional coloring, fractional arboric-ity and fractional isomorphism. Nearly every integer-valued invariant encountered in a first course in graph theory gives to a fractional analogue.This thesis is divided into four chapters. We mainly discuss three problems. (1) Binding number and factors in graphs; (2) toughness and factors in graphs; (3) ID-factor-critical graphs.In Chapter 1, we give a short but complete survey on factors and fractional factors.The binding number of G is defined by Woodall [91] asMany scholars investigated the relationship between binding number and the existence of factors in graphs. In Chapter 2, we pay our attention to binding number related to factors in graphs. We first discuss the relationship between binding number and (g,f)-factors, fractional f-factors and f-factors in K1,n-free graphs, and next we consider the [a,b]-factors in graphs when a< b in terms of binding number, finally, we study binding number and fractional k-factors in graphs.Theorem 2.2.5 Let G be a graph and g, f be integer-valued functions defined on V(G) such that a≤g(x) a> 2, then G contains a (g, f)-factor including e1 and e2.Theorem 3.2.2 Let G be a graph and g, f be integer-valued functions defined on V(G) such that a≤g(x) a> 2, then G contains a (g, f)-factor including e1 and excluding e2.Theorem 3.2.3 Let G be a graph and g, f be integer-valued functions defined on V(G) such that a≤g(x)< f(x)≤b. Let e1=v1v2, e2= v1v2 be two distinct edges of G. where a, b are two positive integers with b> a> 2, then G contains a (g, f)-factor excluding e1 and e2.For [a,b]-factors in graphs, we gave an improvement of the results in ([23]) and ([92]). And we show the results are best possible in some sense.Theorem 3.3.5 Let G be a graph and a, b be two positive integers such that then G has an [a,b]-factor.Theorem 3.3.6 Let a, b be two integers with b> a> 2 and e1=v1v2, e2=v1v2 be two distinct edges of a graph G. then G contains an [a, b]-factor including e1 and e2.Theorem 3.3.7 Let a, b be two integers with b> a> 2 and e1=v1v2, e2=v1v2 be two distinct edges of a graph G. If t(G)≥a-1+(?), then G contains an [a, b]-factor including e1 and excluding e2.Theorem 3.3.8 Let a, b be two integers with b> a> 2 and e1=v1v2, e2=v1v2 be two distinct edges of a graph G. If t(G)≥a-1+(?), then G contains an [a, b]-factor excluding e1 and e2.We also consider (a, b, k)-critical graphs in terms of isolated toughness and show the result is best possible in some sense.Theorem 3.4.1 Let a, b, k be integers with 1≤a