Disjoint cycles of different lengths in graphs and digraphs

Julien Bensmail¹ ; Ararat Harutyunyan² ; Ngoc Khang Le³ ; Binlong Li⁴ ; Nicolas Lichiardopol⁵

¹Université Côte d'Azur, CNRS, Inria, I3S
²Université Paris-Dauphine, PSL Research University, LAMSADE, CNRS
³École Normale Supérieure de Lyon, LIP
⁴Northwestern Polytechnical University
⁵Lycée A. de Craponne, Salon

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

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 \geq 1$, every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ 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.

Détail

DOI : 10.37236/6921

Classification : 05C12, 05C07, 05C20, 05C38
Mots-clés : vertex-disjoint cycles, different lengths, minimum degree