Skip to Main content Skip to Navigation
Journal articles

Edge condition for long cycles in bipartite graphs

Abstract : 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 C, 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(2) + 3/2k + 4, k is an element of 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, May 7, 2014 - 4:21:42 PM
Last modification on : Tuesday, December 7, 2021 - 3:33:14 PM
Long-term archiving on: : Thursday, August 7, 2014 - 11:40:22 AM


Files produced by the author(s)




Lech Adamus. Edge condition for long cycles in bipartite graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, Vol. 11 no. 2 (2), pp.25--32. ⟨10.46298/dmtcs.452⟩. ⟨hal-00988212⟩



Record views


Files downloads