Degree Conditions For Vertex-disjoint Cycles With Given Lengths In Graphs

The degree condition for the existence of cycle(s)with specified length(s)is one of the most elementary concerns in graph theory.A classic result should be the one given by Dirac in 1952,which says that every graph of order n with minimum degree at least n has a Hamilton cycle.Since then,this result has been generalized to various forms in terms of degree condition or degree sum condition.In particular,Ore generalized the Dirac’s result by extending the degree condition to degree sum condition.In the past decades,as an extension of Hamilton cycle,the existence of vertex disjoint cycles with given lengths received much attention.In 1984,EL-Zahar conjectured that,for any integers n1,n2,...,nk no less than 3,every graph of order n=ni+n2+…+nk with smallest vertex degree at least 「n1/2(?)+「n2/2(?)+…+「nk/2(?)has k vertex disjoint cycles of length n1,n2,...,nk,respectively.Lots of progress on this conjecture has been made.Until now,this conjecture still remains open.In this thesis we focus on EL-Zahár conjecture and its relative subjects.The thesis is organized into five chapters as follows.In Chapter 1,we list some basic definitions and notations;review the background and the main improvement of the relative subjects involving specified condition for vertex disjoint cycles in graphs;introduce the main results of the thesis.In Chapter 2,we consider the degree sum condition for the existence of two vertex disjoint cycles with specified lengths in graphs.Let n1,n2 be two integers with n1,n2≥3 and G a graph of order n with n=n1+n2.We show that if σ2(G)≥n+2 then G has two vertex disjoint cycles of length n1 and n2.This gives a positive answer to Yan et.al.’s question,that is,whether the condition σ2(G)≥n+4 can be improved by σ2(G)≥n+2?In Chapter 3,we consider the degree condition for the existence of two vertex disjoint cycles with specified lengths and containing some specified vertices.Let n1 and n2 be two integers with n1,n2≥3.Let G be a graph of order n=n1+n2 and S a set of two vertices in G.We show that if δ(G)≥(n+2)/2,then G contains two vertex disjoint cycles C1,C2 such that |V(Ci)∩S|=1 and |Ci|=nt for 1≤i≤2.In Chapter 4,we show that every graph of order n=5k and σ2≥n+k contains k vertexdisjoint cycles of length 5,where σ2(G)is the smallest degree sum of two non-adjacent vertices in the graph.This gives a positive answer to Chiba and Yamashita’s question on whether the condition 6(G)≥3k can be improved by σ2(G)≥n+k.In Chapter 5,Based on Bondy’s meta-conjecture,we character the degree condition for vertex-pancyclicity of strongly edge-colored graphs.Let G be a strongly edge-colored graph with order n.We show that if δ≥2n/3,then G is rainbow vertex-pancyclic.