# zbMATH — the first resource for mathematics

Disjoint cycles of different lengths in graphs and digraphs. (English) Zbl 1376.05038
Summary: 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 \geqslant 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.

##### MSC:
 05C12 Distance in graphs 05C07 Vertex degrees 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles
##### Keywords:
vertex-disjoint cycles; different lengths; minimum degree
Full Text: