Discrete Mathematics & Theoretical Computer Science, Vol 11, No 2 (2009)

Font Size:  Small  Medium  Large

Edge condition for long cycles in bipartite graphs

Lech Adamus


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 / 2k2 + 3 / 2k + 4, k∈N. 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.

Full Text: PDF PostScript