Some Results On Independent 4-Cycle And 6-Cycle In Graphs

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Ï…in G. Let A(G) and 5(G) denote the maximum and the minimum vertex degree of G, respectively. For a graph G,|G|=|V(G)| is the order of G, andis the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we defineσ₂(G)=∞).For a bipartite graph G with partite sets V₁ and V₂, define(When G is a complete bipartite graph, we defineσ_1,1=∞).When |V₁| = |V₂|, we call G a balance bipartite graph.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)|.A path factor is a spanning subgraph whose components are paths. For a positive integer k, P≥k-factor means a path factor such that each component has at least k vertices.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 perfect 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 cycle, which have no common vertex. The independent cycles, 2-factor and path-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. The discussion is mature and perfect increasingly. And it has important applications in computer science and networks. The study of independent cycles, 2-factor and path-factor theory mostly focus on the following several topics: Graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length, Graph containing independent cycles and 2-factor which have specified properties, and path-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 path-factor, and the progress on the cycle and the path-factor theory. This chapter is the base of the next two chapters.In Chapter 2, we investigate the graph containing independent cycles which have specified properties. In this chapter, the main result is as the following theorem.Theorem 2.1.1. Suppose G is a simple graph with 4k vertices, where A; is a positive integer. Ifσ₂(G)≥4k;-2, then G contains k-1 vertex-disjoint 4-cycles where i = 1,2,…, k-1,and e(i=1^k-1C_i)>)≥2.In Chapter 3, we have the following results.Theorem 3.1.1. Let k≥2 be a positive integer and G be a balance bipartite graph with 6k vertices.If|V₁| = |V₂|=3k andδ_1,1(G)≥4k-1, then G contains k-1 vertex-disjoint 6-cycles.Theorem 3.1.2. Let k≥5 be a positive integer and G be a balance bipartite graph with 6k vertices.If |V₁| = |V₂| = 3k andδ_1,1(G)≥4k-1, then G contains k-2 6-cycles and a 12-cycle such that all of them are vertex-disjoint.Theorem 3.2.1. Let G be a balance bipartite graph.If |V₁|= |V₂| =3k andδ_1,1(G)≥4k + 1,then G contains k 6-cycles.In Chapter 4,we give two counterexamples for a graph satisfying some conditionsto contain independent cycles with specified vertices.Furthermore. In Chapter 2. Chapter 3 and Chapter 4. we list some problems for future research.