Some Results On Independent Cycles And 2-Factors In Graphs

In this paper, we consider both nondirected-graphs and directed-graphs. Let G = (V(G),E(G)) be a nondirected-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, respectively. For a graph G, |G|=|V(G)| is the order of G, and we define the following as the minimum degree sum of two nonadjaccnt vertices:(If G is a complete graph, letσ₂(G)=∞).For a bipartite graphG=G(V₁,V₂;E), if |V₁|=|V₂|, we call G is a balanced bipartite graph. We define the following as the minimum degree sum of two nonadjacent vertices from different partition:(If G is a complete bipartite graph, letσ_1.1(G)=∞)。In a directed graph D = D(V(D),A(D)), V(D) and A(D) denotes the vertex set and directed-edge set respectively. E(D) denote the reversible-edge set in D. |A(D)|and|E(D)| denotes the number of directed-edges and reversible-edges respectively.d_D⁺(v)and d_D^-(v) denotes the out-degree and in-degree respectively, and d_D(v) denote the sum the in-degree and out-degree of v.The complete bipartite graph K_1,3 is called a claw, and G is said to be claw-free if G has no induced subgraph isomorphic to K_1,3. Let P be a path and C a cycle. We denote the length of P and the length of C by l(P) and l(C), respectively. That is, l(P) = |V{P)|-1, l(C) = |V(C)|. For any two vertices x and y, the distance from x to y is the length of the shortest path from x to y, denoted by d(x,y).A Hamilton cycle of G is a cycle of G which contains every vertex of G. A 1-factor of a graph G is a 1-regular spanning subgraph of G, and we call a 1-factor a perfcct matching. It is readily seen that a 1-factor of G is a collection of independent edges that covers all vertices of G. A 2-factor of G is a 2-regular spanning subgraph of G. Clearly, each component of a 2-factor of G is a cycle, k independent cycles of G are k cycles which have no common vertex.The independent cycles, and 2-factor theory in G are important problems in graph factorial theory, also they are the extending of Hamilton cycle theory. It is an interesting problem in graph theory, and it is an international hot topic. The discussion is mature and perfect increasingly. And it is important applications to computer science and network. The study of independent cycles, 2-factor and path-factor theory mostly focus on following: Graph containing specificd number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length.and Graph containing indepcndent cycles and 2-factor which have specified properties, etc.The paper is divided into four chapters. In Chapter 1, we introduce some basic notations, the history of the cycle theory and the progress on the cycle theory. This chapter is the base of the next three chapters.In Chapter 2, we investigate the number of quadrilaterals in a graph satis-fying given degree condition. In this chapter, the main result is as the following theorems.Theorem2.3.1. Let G be a nondirected graph of order 4k, andσ2≥4k-2, then G contains k-1 disjoint quadrilaterals.In Chapter 3, we discuss a kind of 2-factor comprises of 4-cycles and 8-cycles. And the main result is the following theorem:Theorem3.3.1. Let G be a balanced bipartite graph of order 4k satisfyingσ1.1(G)≥2k+1. Then G contains k-2 4-cycles and one 8-cycle, and the k -1 cycles are vertex-disjoint.In Chapter 4, we discuss the existing condition and the number of di-quadrilaterals in a directed-graph. And the main result is the following theorem:Theorem4.3.1. Let D be a directed-graph of order n≥4k, and D satisfys thedegree conditionδ(D)≥(?), then D contains k vertex-disjoint di-quadrilaterals, with the exception that: n = 4k + r, k is odd, r∈{0,2}, D≌(?)→(?).