Disjoint Cycles With Specific Properties In Graphs

In this paper, we mainly discuss the disjoint cycles with specific properties in graphs.A path or a cycle with k vertices in a graph G is called k-path or k-cycle. If a path (or a cycle) contains all the vertices of G, then we call this path (or this cycle) a Hamilton path (or a Hamilton cycle). Disjoint cycles in a graph is the generalization of the well-known Hamilton cycle theory. Catlin (Ph. D. Dissertation. Ohio State University,1976), Aiger, Brandt (J. London Math. Soc,1993,48(2):39-51) and Alon (Discrete Mathematics,1996,152(1):13-23) gave the degree condition of a graph contains disjoint cycles, respectively. In 1984, El-Zahar conjectured that if G is a graph of order n=ni+n2+…+nk (ni≥3,1≤i≤k) and then G contains k disjoint cycles C1, C2,…, Ck of length n1,n2,…, nk, respectively. This con-jecture is still open. But El-Zahar proved this conjecture for the case of k= 2 in the same paper:If a graph G of order n= n1+n2 with ni≥3 for all i and then G contains two disjoint cycles of length n1 and n2, respectively. In 2009, Gao, Yan and Li (J. Appl. Math Comput.2009, 31:203-215) gave the degree condition of the disjoint cycles containing speci-fied vertices in a bipartite graph. In this paper the following results are proved:Result 1:Let G be a simple graph on n vertices. If d(x)+d(y)≥n+4 for any two vertices x,y ∈V(G) with xy (?)E, then for any (n1,n2), ni≥3, n=n1+n2, G contains two disjoint cycles of length n1 and n2, respectively.Result 2: Let k be a positive integer and let G be a simple graph on n≥4k vertices. If max{d(x),d(y)}≥2k for any pair of x, y∈V(G) with xy(?)E, then G contains k disjoint cycles.Result 3: Let G = (V1,V2,E) be a bipartite graph with |V1| = |V2| = n≥ 2k + 1, where k≥1 is an integer. If d(x) + d(y)≥n + k for any two vertices x∈V1,,y∈V2 with xy(?)E, then for any k distinct vertices v1,v2,…,vk of G, G contains k-1 quadrilaterals C1, C2, …, Ck-1 and a path Pk of order 2t, where t = n— 2(k — 1) such that all of them are disjoint and v1∈V(Ci) for each i∈{1,2,…,k-1}, vk∈K(Pk).Result 4: Let G = (V1,V2,E) be a bipartite graph with |V1| = |V2| = n≥ 2k + 1, where k ≥1 is an integer. If d(x) + d(y)≥n + k for any two vertices x∈V1,y∈V2 with xy(?)E, then for any k distinct vertices v1,v2,…,vk of G, G contains k disjoint C1,C2,…,Ck such that vi∈V(Ci) for each i∈{1,2,…, k} and there are k - 1 quadrilaterals in {C1,C2,…, Ck}.