Disjoint cycles covering specified vertices in bipartite graphs with partial degrees


Abstract in English

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 $xin S, yin Y$ satisfies $d(x)+d(y)geq n+1$. We show that if $|S|geq 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$.

Download