Article ID Journal Published Year Pages File Type
4650016 Discrete Mathematics 2009 6 Pages PDF
Abstract

Let k≥1k≥1 be an integer and G=(V1,V2;E)G=(V1,V2;E) a bipartite graph with |V1|=|V2|=n|V1|=|V2|=n such that n≥2k+2n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V1x∈V1 and y∈V2y∈V2, d(x)+d(y)≥⌈4n+2k−13⌉, then for any kk independent edges e1,…,eke1,…,ek of GG, GG has a 2-factor with k+1k+1 cycles C1,…,Ck+1C1,…,Ck+1 such that ei∈E(Ci)ei∈E(Ci) and |V(Ci)|=4|V(Ci)|=4 for each i∈{1,…,k}i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,