Some Topics On Cycles With Given Length And Universal Arcs Of Graphs

The study of graph theory started over two hundred years ago. The earliest known paper is due to Euler in 1736, who solved the seven bridges of Konigsberg by graph theory. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and celebrated problems in graph theory, such as euler problem, hamiltonian problem, Chinese postman problem, four-color problem, etc. It is of great advantage to apply graph theory to resolve problems in operational research, physics, chemistry, biology, network theory, information science, game theory and other disciplines. As a subfield in discrete mathematics and combinatorial mathematics, graph theory has attracted much attention from all perspectives.All graphs considered in this thesis are finite, simple graphs without loops or multiple edges. Let G be a graph on n vertices and H be a graph on h vertices, where n, h are positive integers. The packing problem in graph theory is to find in G as many vertex-disjoint copies of H as possible. An H-factor of G is a subgraph of G which consists of [n/h]copies of H. In particular, a k-factor in a graph G is a spanning k-regular subgraph of G, where k is a positive integer. In our daily life, many problems on optimiza-tion and network design, e.g., coding design, building blocks, structure of DNA, scheduling problems and so on, are related to the factors and factor-izations. We mainly focus on the existence of 2-factor throughout this thesis. A cycle is called k-cycle, if it has exactly k vertices; a path is called k-path, if it has exactly k vertices. In particular, a 3-cycle is called triangle, a 4-cycle is called quadrilateral and a 6-cycle is called hexagon. A cycle which contains every vertices of the graph is called a Hamiltonian cycle. Obviously, a Hamiltonian cycle is a 2-factor with exactly one component. In 1952, G. Dirac gave a minimum degree condition that ensure a graph contains a Hamil-tonian cycle. In 1960, O. Ore put forward a minimum degree-sum condition that ensure a graph contains a Hamiltonian cycle. These two results can be viewed as a forerunner of 2-factor theory. For a given graph, it is a more complex procedure to find the condition to ensure the existence of 2-factor. The most usual technique to resolve 2-factor problems is to find a minimal packing and then extend it to a required 2-factor.This thesis is concerned with some problems of graph theory. In particu-lar, our aim is to discuss the existence of vertex-disjoint subgraphs(particular cycles and paths) and 2-factor in a given graph, the existence of universal arcs in a directed graph. Many of them can be described as follows:What condi-tions on minimum degree (or degree-sum) are sufficient to make sure that G contains a 2-factor? Further, can we determine the number of cycles in the 2-factor, or the length of these cycles, or both from these conditions? The above problem is the fundamental question in extremal graph theory. In this thesis, we consider minimum degree and degree-sum conditions that ensure a graph contains quadrilaterals, or hexagons, or 8-cycles. An arc e is called universal in a digraph D, if for every vertex x∈V(D), there exists a cycle containing both the arc e and the vertex x. Clearly, if a digraph D contains a Hamiltonian cycle, then every arc in the Hamiltonian cycle is universal. We consider minimum degree condition that make sure strong-connected multi-partite tournaments and cycle-connected multipartite tournaments contain universal arcs. We have constructed our work on five chapters.A short but complete introduction about the thesis is mainly given in chapter 1. First, we present all the basic concepts and symbols, then we describe the background and progress about vertex-disjoint subgraphs and cycles with given length in graphs. Next, we introduce the progress about universal arcs in digraphs. Finally, we outline the main results of our thesis.In chapter 2, we give degree conditions that ensure a graph contains vertex-disjoint quadrilaterals. First, we define two kinds of graph:M(k1, k2)= K4k1+2∪K4k2+2 and N(k1,k2)= K4k1+1∪K4k2+3, where k1, k2 are two nonnegative integers. Let G be a claw-free graph with|G|= 4k, where k is a positive integer. If the minimum degree-sumσ2(G)≥4k - 2, we show that G has a spanning subgraph consisting of k - 1 vertex-disjoint quadrilaterals and a 4-path such that all of them are vertex-disjoint, unless G(?)M(k1,k2) or G(?)N(k1,k2), where k1≥0, k2≥0, k1+k2= k-1. We also prove that the degree condition is sharp and the condition of G being claw-free is indispensable. Moreover, we give a degree condition that ensure a bipartite graph contains quadrilaterals. Let G= (V1,V2; E) be a bipartite graph with|V1|=|V2|= 2k, where k> 0 is a positive integer. We show that if d(x)+d(y)≥3k for every pair nonadjacent of vertices x∈V1, y∈V2, then G contains k vertex-disjoint quadrilaterals.We begin chapter 3 with the problems of vertex-disjoint hexagons in a bipartite graph. Let G= (V1; V2; E) be a bipartite graph with|V1|=|V2|=3k, where k is a positive integer. First, we show by minimum degree condition that, if the minimum degree of G is at least 2k, then G either contains k vertex-disjoint hexagons, or contains k - 1 vertex-disjoin hexagons and a quadrilaterals, such that all of them are vertex-disjoint. Secondly, we put forward degree-sum conditions that guarantee the existence of hexagons in a bipartite graph. Let G= (Vi, V2;E) be a bipartite graph with|V1|=|V2|=3k, where k is a positive integer. We prove that, if d(x)+d(y)≥4k - 1 for every pair nonadjacent of vertices x∈V1, y∈V2, then G contains k - 1 vertex-disjoint hexagons and a 6-path such that all of them are vertex-disjoint; if k> 2 and d(x)+d(y)≥4k for every pair nonadjacent of vertices x∈Vi, y∈V2, then G contains k - 2 vertex-disjoint hexagons and a 12-cycle such that all of them are vertex-disjoint.In chapter 4, we are interested in degree conditions that guarantee the existence of chorded 8-cycles in a bipartite graph. To do this, we first find a 2-factor each component of which is a 8-cycle, then revise the edges such that each 8-cycle contains at least two chords. Our result is as follows:Let G= (Vi, V2; E) be a bipartite graph with|V1|=|V2|=4k, where k is a positive integer. If the minimum degree of G is at least 3k+1, then G contains k vertex-disjoint cycles of order eight such that each of them has at least two chords.Finally in chapter 5, we consider universal arcs in a digraph. Volkmann showed that every strong-connected multipartite tournament with minimum degreeδ≥2 has a universal arc in its longest cycle. We give an extension of Volkmann’s result. Let D be a multipartite tournament. If D is strong-connected with minimum degree at least 2, then every longest cycle of D contains at least two universal arcs; if D is cycle-connected with minimum degree at least 2, then every longest cycle of D contains at least two universal arcs.