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
Liste complète des métadonnées

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-00988212
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, May 7, 2014 - 4:21:42 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:17 AM
Document(s) archivé(s) le : Thursday, August 7, 2014 - 11:40:22 AM

File

945-4294-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00988212, version 1

Collections

Citation

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

Share

Metrics

Record views

458

Files downloads

600