| 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. There are many nice and celeberted problems in graph theory,such as hamiltonian problem,four-color problem,chinese postman problem,etc.Moreover,graph theory is widely applied in chemistry,computer science,biology and other disciplines.As a subfield in discrete mathematics,graph theory has attracted much attention from all perspectives.All graphs are considered only finite,simple,undirected graphs with no loops and no multiple edges.Let G be a graph.The Hamiltonian cycle problem is one of the most well-konwn problems in graph theory.A cycle which contains every vertex of G is called a Hamiltonian cycle.A k-factor in a graph G is a spanning k-regular subgraph of G,where k is a positive integer.There exists many interesting results about the existence of k-factor,by applying Tutte's Theorem,however,we mainly focus on the existence of 2-factor throughout this thesis.Clearly,a Hamiltonian cycle is a 2-factor with exactly one component.From this point of view,it is a more complex procedure to find the condition to ensure the existence of 2-factor in a given graph.The most usual technique to resolve 2-factor problems is to find a minimal packing and then extend it to a required 2-factor.The thesis is concerned with some problems of graph theory.More specifically, our aim is to discuss some topics on k-factor which contains a Hamiltonian cycle, the existence of disjoint subgraphs(particular cycles) and 2-factor in a given graph G.Many of them can be described as follows:Let F be a connected graph with given specified graphic structure,and let k be an positive integer,what is the minimum degree condition or minimum degree sum condition to ensure a graph G with |V(G)|≥k|V(F)| contain k vertex-disjoint copies of F? The above problem is the fundamental question in extremal graph theory.For a noncomplete graph G,defineσ2(G):=min{dG(x)+ dG(y)|xy(?)E(G)};if G is a complete graph,letσ2(G):=∞.We have constructed our work on eight chapters.A short but relatively complete introduction about the thesis is mainly given in chapter 1.First,we present basic concepts and definitions.Then we describe the background and progress about 2-factor theory and disjoint cycles. Finally,we outline the main results of our thesis.We begin Chapter 2 with the problem of the existence of k-factor which contains a given Hamiltonian cycle.Let k be an integer with k≥2 and let G be a graph having sufficiently large order n.Suppose that kn is even,the minimum degree of G is at least k and max{dG(x),dG(y)}≥(n+α)/2 for each pair of nonadjacent vertices x and y in G,whereα=3 for odd k andα=4 for even k.We show that G has a k-factor(i.e.a k-regular spanning subgraph) which contains a given Hamiltonian cycle C if G-E(C) is connected.We also prove that the degree condition is sharp and the connected requirement is necessary by constructing examples.In chapter 3,we are interested in degree conditions that guarantee the existence of the 2-factor in a bipartite graph G such that each component is a quadrilateral and passing through a specified vertex.To do this,we first find a vertex-disjoint packing of G such that each component is either a quadrilateral or a cycle of length six,then we extend it to a desired 2-factor.The proof is constructive and our result is as follows:Let k be a positive integer and G=(V1,V2;E) a bipartite graph with |V1|=|V2|=n≥2k+2. Suppose dG(x)+dG(y)≥[(4n+k)/3]for any nonadjacent vertices x∈V1 and y∈V2,then for any k distinct vertices z1,…,zk,G contains a 2-factor with k+1 cycles C1,…,Ck+1 such that zi∈V(Ci) and |Ci|=4 for each i∈{1,…,k}.The main focus of chapter 4 is to investigate the minimum degree sum to ensure the existence of the 2-factor,which each component is isomorphic a chorded quadri- lateral.In fact,we show that if a graph G of order n≥4k+3 withσ2(G)≥n+k,then G contains a 2-factor with k+1 disjoint cycles C1,…,Ck+1 such that Ci are chorded quadrilateral for 1≤i≤k-1 and the length of Ck is at most four.Moreover,we show that if a graph G of order n＞4k withσ2(G)≥n+k,Then G contains a 2-factor with exactly k disjoint cycles such that k-1 of them are chorded quadrilateral.In addition, we prove the bound for the order and the degree sum are best possible.In chapter 5,we consider the packing problem for vertex-disjoint triangles and quadrilaterals.We prove that,for a graph G with order n≥3s+4(k-s),where s and k be two positive integers such that 1≤s≤k,ifσ2(G)≥n+s,then G contains k disjoint cycles C1,…,Ck such that |Ci|=3 for 1≤i≤s and |Ci|=4 for s＜i≤k. In particular,when the order of G is exactly 3s+4(k-s),then G contains a 2-factor with exactly k components such that s of them are triangles and k-s of them are quadrilaterals.In chapter 6,we show that a graph G with order at least 4k andσ2(G)≥6k-1, then G contains k disjoint chorded cycle,where k is a positive integer.The above result is a generalization of Finkel's result in the spirit of Enomoto and Wang's generalization of Hajnal and Corradi.In chapter 7,based on the main result in chapter 6,we show that every graph G of order at least 3r+4s andσ2(G)≥4r+6s-1,then G contains a collection of r cycles and s chorded cycles,all vertex-disjoint,where r and s are two nonnegative integers.Asσ2(G)≥2δ(G),the above theorem verified a conjecture proposed by A. Bialostocki,D.Finkel and A.Gyarfas.Finally,in chapter 8,we consider some extensions of early results by virtue of Neighborhood unions condition,which is a more stronger measure that minimum degree condition in graphs.
|
PDF Full Text Request