On Covering a Bipartite Graph with Cycles
Hong Wang · SIAM Journal on Discrete Mathematics · 2001
We conjectured in [H. Wang, Australas. J. Combin., 19 (1999), pp. 115--121] that, for each integer $k\geq 2$, there exists N(k) such that if G=(V 1 ,V 2 ;E) is a bipartite graph with $|V_1|=|V_2|=n\geq N(k)$ and d(x)+d(y)\geq n+k$ for each pair of nonadjacent vertices x and y of G with $x\in V_1$ and $y\in V_2$, then for any k independent edges e 1 , . . ., e k of G, there exist k vertex-disjoint cycles C 1 , . . . ,C k in G such that $e_i\in E(C_i)$ for all $i\in\{1,\ldots ,k\}$ and $V(C_1\cup\cdots \cup C_k)=V(G)$. This conjecture is also verified for k=2 in [H. Wang, Australas. J. Combin., 19 (1999), pp. 115--121]. We prove this conjecture for k=3 in this paper.