Edge condition for long cycles in bipartite graphs.

The following problem was solved by Woodall in 1972: for any pair of nonnegative integers n and k < n/2 - 1 find the minimum integer g(n, k) such that every graph with n vertices and at least g(n, k) edges contains a cycle of length n - k. Woodall proved even more: the size g(n, k), in fact, guarantees the existence of cycles Cp for all 3 ≤ p ≤ n - k. In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n; m ≤ n; and size greater than n(m - k - 1) + k + 1 contains a cycle of length 2m - 2k, where m ≥ 1/2k² + 3/2k + 4; k ∈ ℕ. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m - 2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m ≥ 2k + 2. [ABSTRACT FROM AUTHOR]