Disjoint cycles of different lengths in graphs and digraphs
Bensmail, Julien; Harutyunyan, Ararat; Le, Ngoc Khang; Li, Binlong; Lichiardopol, Nicolas (2017), Disjoint cycles of different lengths in graphs and digraphs, The Electronic Journal of Combinatorics, 24, 4, p. 4.37. 10.37236/6921
TypeArticle accepté pour publication ou publié
Journal nameThe Electronic Journal of Combinatorics
MetadataShow full item record
Inria Sophia Antipolis - Méditerranée [CRISAM]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Le, Ngoc Khang
Laboratoire de l'Informatique du Parallélisme [LIP]
Department of applied mathematics
Abstract (EN)In this paper, we study the question of finding a set of k vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every k≥1, every graph with minimum degree at least k2+5k−22 has~k vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider other cases such as when the graph is triangle-free, or the k cycles are required to have different lengths modulo some value r. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have k vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for some regular digraphs and digraphs of small order.
Subjects / Keywordsminimum degree; vertex-disjoint cycles; different lengths
Showing items related by title and author.
Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019) Article accepté pour publication ou publié