Disjoint cycles covering specified vertices in bipartite graphs with partial degrees

Abstract

Let $k$ be a positive integer. Let $G$ be a balanced bipartite graph of order $2n$ with bipartition $(X,Y)$, and $S$ a subset of $X$. Suppose that every pair of nonadjacent vertices $(x,y)$ with $x\in S,y\in Y$ satisfies $d(x)+d(y)\ge n+1$. We show that if $|S|\ge 2k+2$, then $G$ contains $k$ disjoint cycles covering $S$ such that each of the $k$ cycles contains at least two vertices of $S$. Here, both the degree condition and the lower bound of $|S|$ are best possible. And we also show that if $|S|=2k+1$, then $G$ contains $k$ disjoint cycles such that each of the $k$ cycles contains at least two vertices of $S$.

19 pages, 4 figures