Some Results On Hamiltonian [a,b]-Factors Of Graphs

Graph theory has witnessed unprecedented. It is of great advantage to applyit in many disciplines, the research about graph factor became an important branch and lots of results on factor theory were sprung forth. Fractional graph theory is a relatively younger branch of modern graph theory. It promoted greatly the development of classic graph theory. By introducing and developing the fractionalidea, two obvious effect came into being, firstly, the scope of applications was enlarged, and secondly, the classic graph theory's construction was more systemic.All graphs considered in this paper are finite simple graphs. 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(v) to stand for the degree of v in G. Let△(G) andδ(G) denote the maximum and the minimum vertex degree of G. For any S(?)V(G), the remaining subgraph of G obtained by deleting all the vertices in S and all the edges incident with the vertices in S is denoted by G-S. If S = {v},v∈V(G), we usually denote G-v= G-{v}. For any X(?)E(G), the remaining subgraph of G obtained by deleting all the edges of X is denoted by G - X. If X = {e},e∈E(G), we usually denote G-e=G-{e}. We call a graph G a bipartite graph if the vertex set of G can be partitioned into two subsets X and Y, so that each edge has one end in X and the another end in Y, such a graph is denoted by G = (X,Y,E(G)); G = (X,Y,E(G)) is called balanced if |X| = |Y|.Let g, f be two integral functions defined on V(G) and g(v)≤f(v), for any v∈V(G). Let H be a spanning subgraph of G. We call H a (g,f)-factor of G ifSimilarly, H is a [a, b]-factor of G, if a≤d_H(v)≤b, for any v∈V(H)(= V(G)), where a and b are two nonnegative integers, and H is a k-factor of G if d_H(v) = k for any v∈V(G), where k is a positive integer. A 1-factor of G is in fact a perfect matching. We call a factor of G a Hamiltonian factor if it contains a Hamiltonian cycle of G. For a graph G, its order is |V(G)|, and we often denote it by n. We call a graph n/2 -critical ifδ(G)≥n/2 andδ(G-e)＜n/2 for any e∈￡(G).Let h(e)∈[0,1] be a function denned on E(G). Let d_G~h(v)=(?), where E_v={e:e=vw∈E(G)}. We call d_G~h(v) the fractional degree of v in G. We call h a indictor function if g(v)≤d_G~h(v)≤f(v) for any v∈V(G), Let E~h={e∈E(G):h(e)≠0} and G_h be a spanning subgraph of G such that E(G_h)=E~h, then we call G_h a fractional (g, f)-factor and h is the indictor function of G_h. Similarly, we can define the fractional [a, b]-factor, the fractional [a, b]-factor and the fractional Hamiltonian factor.Let f(v) be any function on V(G), we define f(S)=(?).In 1947, Tutte got a sufficient and necessary condition for graphs to have a 1-factor, which was considered as the most fundamental result in factor theory. Generalizing this result, in 1952, he gave a criterion again in his f-Factor Theory. Then in 1970's, Lovasz got a necessary and sufficient condition for the existence of (g, f)-factor in graphs.In this paper, we'll try to give some results about Hamiltonian factors and fractional Hamiltonian factors of graphs.As we know, a Hamiltonian cycle of a graph can be considered as a 2-factor of the graph which contains only one cycle. So by this conception of Hamiltonian cycle, it is obvious that we can take a Hamiltonian cycle of any given graph G as a 2-factor of the graph which containing some Hamiltonian cycle (in fact is itself) of G. Then we can get the following question immediately, Can we get some sufficient conditions for the exist of special factors which containing some (maybe any given) Hamiltonian cycle of G. This is the root of the results we got in this paper. The special factors mentioned above should be more trivial in general, it can be a [a, b]-factor or a fractional [a, b]-factor. In fact, all the results we got in this paper are the sufficient condition for the exist of such special factors mentioned above.There are two reasons for us to make research on Hamiltonian factors, first, it can give a help to our study of Hamiltonian circuits, and second, it can help us a lot to resolve the problems about connected factors. Obviously, a graph has a connected factor if it has a Hamiltonian factor (in fact, it has a 2-connected factor). And that is just the reason why people pay their attention to Hamiltonian factors.The paper is divided into three chapters. In Chapter One, we introduce some basic conceptions of graph theory, the history and some new advances on factors, fractional factors and Hamiltonian circuits. This chapter is the base of following chapters.Chapter Two is major in Hamiltonian factors. The main results are the following theorems.Theorem 2.1.1. Let G = (X,Y,E(G)) be a bipartite graph of order n, G is balanced (|X|=|Y|) andδ(G)≥n/4+1. Let b≥a≥2 be an integer and n≥4(a+b)-23. Then for any given Hamiltonian cycle C, G has a [a, b]-factor containing C.Theorem 2.2.1. Let G be a graph with no cut edge and its order n≥3 with b＞a≥2,δ(G)≥a. n≥4(a+b)-20 for even n and n≥3(a+b)-16 for odd n. If for each pair of nonadjacent vertices u and v of V(G)Then for any given Hamiltonian cycle C, G has a [a, b]-factor containing C.Theorem 2.3.4. Let b＞a≥2 be an integer and let G be a graph of order n, n≥3(a+b) - 8,δ(G)≥(?). Then1. for any given Hamiltonian cycle C and edge e∈E(G), G has a [a, b]-factor contains e and C.2. for any given Hamiltonian cycle C and edge e∈E(G), e(?)E(C), G always has a [a, b]-factor such that the factor contains C while not e.Chapter Three gives two results about fractional Hamiltonian [a, b]-factors in general graphs. The main results are as following:Proposition 3.1.1. Let G be a graph of order n with a≥1,b≥a+2, andn≥(?) .If for each pair of nonadjacent verticesu and v of V(G)then G has a fractional Hamiltonian [a,b]-factor.Theorem 3.2.1. Let b≥a≥2 be an integer and let G be a graph of order n≥3,δ(G)≥a. n≥3(a+b)-13 for even n and n≥3(a+b)-12 for odd n. If for each pair of nonadjacent vertices u and v of Gthen for any given Hamiltonian cycle C, G has a fractional [a, b]-factor containing C.Theorem3.2.2. Let b≥a≥2 be an integer and let G be a graph of order n. G is (n/2+1)-critical and n≥2(a+b)-9 for even n, G is ((?)+2)-critical and n≥2(a+b)-12 for odd n. Then for any given Hamiltonian cycle C, G has a fractional [a, b]-factor containing C.Furthermore, in Chapter Two and Chapter Three, we list some problems for future research.