Some New Results On Independent Cycles And 2-Factor 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 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σ₂(G) = min{d_G(x)+d_G(y)|x,y∈V(G),x≠y,xy (?) E(G)}is the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we defineσ₂(G) =∞).For a vertex u of G, the neighborhood of u are denoted by N_G(u) = {x∈V(G)|xu∈E(G)} .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)|.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 cycles which have no common vertex.The theory of independent cycles and 2-factor of graphs is the extending of Hamilton cycle theory. It is an interesting problem in graph theory. Furthermoreit has important applications to computer science and networks. The study of independent cycles and 2-factor theory mostly focuses on the following: Aspects graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length,and Graph containing independent cycles and 2-factor which have specified properties, etc. The paper is divided into three chapters. In Chapter 1, we introduce some basic notations, the history of the cycle theory . This chapter is the base of the next two chapters.Concerning independent cycles containing specified length, Yan Jin[17] proved the next result . Let s and k be two positive integers with s≤k, and let G be a graph of order n≥3s + 4(k - s) + 3. Ifσ₂(G)≥n + s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4 for s < i≤k. In Chapter 2, we have the following result.Theorem2.1.1. Let s and k be two positive integers with s≤k, and let Gbe a graph of order n≥3s + i(k - s) + 3. Ifσ₂(G)≥n + 2k - s+3/2, then G contains k disjoint cycles C₁ ,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4, |E(C_i)|≥5 for s1+n₂ + 1, and n₁≥3,n₂≥3.Ifδ(G)≥(?)3n₁/4(?)+(?)3n₂/4(?)+ 1, then G contains two disjoint cycles C₁, C₂ satisfying |C₁| =n_i + 1, |C₂| = n_j(i,j = 1,2), and (?)e∈G we have e∈E(C₁) or e∈E(C₂).