On covering a bipartite graph with cycles (Q2784504)

Let \(k\geq 2\) be a fixed integer and \(G\) be a bipartite graph with parts of size \(n\) and the property that for every nonadjacent pair of vertices from different parts the sum of their degrees is at least \(n+k\). The author of this paper conjectured [Australas. J. Comb. 19, 115-121 (1999; Zbl 0927.05064)] that for every integer \(k\geq 2\) there is a (minimal) integer \(N(k)\) such that if \(n\geq N(k)\) and \(k\) independent edges in \(G\) are given, then we can find \(k\) vertex-disjoint cycles which cover the vertex set of \(G\) and have the property that every cycle contains exactly one of the specified edges. In that same paper the author shows that \(N(2)=5\). In the current paper the case \(k=3\) is solved. It is established that \(N(3)=8\), and all \(G\) with \(n\leq 7\) which need not contain three such cycles through specified edges are determined.