Related Problems Of Disjoint Cycles In Graphs

We discuss some problems related to disjoint cliques with specific proper-ties in a graph and disjoint cycles in a bipartite graph.Let G be a graph.The order of G is |V(G)| and its size is |E(G)|.Let v ? V(G),let dG(v)denote the degree of v.The minimum degree of G is denoted by ?(G).The maximum degree of G is denoted by ?(G).We define?2(G)= min{d(x)+ d(y)|x ? V,y ?V,xy(?)E}.We say k graphs can be packed if there exist edge disjoint embeddings of the k graphs into the com-plete graph Kn.In particular,it is called 2-packing if k = 2.Vertex-disjoint subgraphs is a special case of 2-packing.A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacen-t;that is,its induced subgraph is complete.In 1963,Erdos gave a conjecture about k disjoint cliques in graphs:let G be a graph of order n with n = sk,where s?3 and k?1 are positive integer.If ?(G)?(s-1)k,then G includes k disjoint Ks.In 1978,Bollobas proved that:let G be a graph of order n with n = 4k,where k is a positive integer.If ?(G)?3n/4,then G contains k disjoint 4-cliques.Recently,Wang proved that:suppose that ?(G)?[n/2],then G contains k disjoint cycles,where k-1 of them are 4-cycles.Extending 4-cycles to 4-cliques,we have researched on disjoint cliques with specific properties in a graph and got the following results:Result 1:Let G be a graph of order n with n ? 4k,where k is a positive integer.Suppose that ?(G)?3n/4,then the partition of G can be k-1 disjoint 4-cliques and a chordal cycles,where the degree of each vertices in this chordal cycle is equal or greater than 3.For a bipartite graph G =(V1,V2;E),two kinds of degree sum are defined as follows:andIf a path(or a cycle)contains all the vertices of G,then define this path(or this cycle)as a Hamilton path(or a Hamilton cycle).Disjoint cycles in a graph is a generalization of Hamilton cycle theory.In 1952,Dirac proved every graph of order n of minimum degree at least[n/2-]is hamiltonian.In 1963,Corradi and Hajnal proved the following theorem:let G be a graph of order n with n>3k,where k is a positive integer.For bipartite graphs,Wang proved the following result:if G =(Vi,V2;E)is a bipartite graph with|V1| = |V2|= n ? 2k + 1 and ?(G)? k + 1,then G contains k disjoint cycles.Enomoto put forward the following problems if it is possible to replace the assumption on ? with ?2,2 and ?1,1.In 2009,the case that replacing ? with?1,1 was proved by Yan and Gao.We substitute ?2,2 for ? and study further problems linked to disjoint cycles in a bipartite graph.In this paper,we prove the following result:Result 2:Let k,n be two positive integers,and let G =(V1,V2;E)be a bipartite graph with |V1|=|V2| =n?4k + 4.If ?2,2(G)? 4k + 4,then G contains k disjoint cycles.