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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (2), pp.25--32
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00988212
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 16:21:42
Dernière modification le : mercredi 29 novembre 2017 - 10:26:17
Document(s) archivé(s) le : jeudi 7 août 2014 - 11:40:22

Fichier

945-4294-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

444

Téléchargements de fichiers

375