Vertex Disjoint Subgraphs In Graphs And Digraphs

In this paper,we mainly consider the existence of disjoint subgraphs,including partition,vertex disjoint cycles and vertex disjoint cycles of different lengths.Let D be a digraph.The minimum out-degree and the minimum semi-degree of D are denoted by δ+(D)and δ0(D),respectively.For a subset X(?)V(D),we use D[X]to denote the subdigraph induced by X.Let k be a positive integer,if there exist V1,…,Vk(?)V(D)such that Vi∩Vj=(?) for any 1≤i≠j≤k,then the subdigraphs D[V1],…,D[Vk]are vertex disjoint.If Vi,…,Vk still satisfy V(D)=V1∪…∪Vk,then we say that V(D)can be partitioned into V1,…,Vk.For any vertex v∈V(D),if the out-degree and in-degree of v both are r,then D is an r-regular digraph.A semicomplete digraph(tournament)is a digraph that there exists at least(only)one arc between any two vertices.In 2016,Alon proposed a problem if there exists a function F(d1,…,dk)for a digraph D such that if δ+(D)≥F(d1,…,dk),then V(D)can be partitioned into V1,…,Vk withδ+(D[Vi]）≥ di for each i ∈[k]?We prove that if the maximum in-degree is bounded,then F(di,...,dk)≤2(d1 +…+dk)by using Lovász Local Lemma.Result 1.Let d1,...,dk be k non-negative integers with lnk/2<d1≤…≤dk and let s=d1+…+dk.Suppose that D is a digraph of minimum out-degree δ+(D)≥ 2s and maximum in-degree Δ-(D)≤min{eδ+(D)d1/12s/4δ+(D),eδ+(D)d1/s/4kδ+(D)},then V(D)can be partitioned into V1,...,Vk such that δ+(D[Vi])≥ di for any i∈[k].Furthermore,we consider limiting the minimum semi-degree of each D[Vi],we prove that some regular digraphs,and digraphs of small order can be partitioned into V1,...,Vk such that δ0(D[Vi])≥ di for i∈[[k].Result 2.Suppose that d1,…,dk are k non-negative integers with d1≤…≤dk and let s=d1+…+dk.Then V(D)can be partitioned into k parts V1,...,Vk such thatδ0(D[Vi])≥ di for each i∈[k],if one of the following holds.(ⅰ)d1≥12,k≥10 and D is an r-regular digraph with r≥2s2/d1.(ⅱ)D is a digraph of order n<erd/4 and minimum semi-degree r≥c0s1/1-d,where d is a constant with 0<d<1 and c0=max{ln 2k,(12)1/1-d}.Based on the results of partitioning in digraphs,we show that a digraph contains k vertex disjoint cycles of different lengths under the conditions of minimum out-degree and maximum in-degree.In addition,we also consider vertex disjoint cycles of different lengths in semicomplete digraphs and tournaments.We give the following results.Result 3.Let D be a semicomplete digraph but not a tournament.If δ+(D)≥k2+3k-2/2,then D contains k disjoint cycles of different lengths.Further,the lower bound of minimum out-degree is tight.Result 4.Let T be a tournament If δ+(T)≥7,then T contains three disjoint cycles of different lengths.We also consider vertex disjoint cycles in graphs in this paper.Let G be a graph.The order of G is denoted by |G|.If any two vertices in X(?)V(G)are not adjacent in G and |X|=t,then X is a t-independent set of G,where t>2.For an integer t≥2,letσt(G)=min{(?)(x,G):X is a t-independent set of G}.In this paper,we prove the following two results which improve the lower bound of |G| of the results of Ma et al.and Gould et al.,respectively.Result 5.Let k≥3 and t≥4 be two integers.Suppose that G is a graph of order|G|≥ kt+1.5k+t and σt(G)≥ 2kt-t+1.Then G contains k disjoint cycles.Result 6.Let k≥2 be a integer.Suppose that G is a graph of order |G|≥5.5k+4 andσ4(G)≥8k-3.Then G contains k disjoint cycles.