Disjoint cycles of different lengths in graphs and digraphs (Q1684653)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disjoint cycles of different lengths in graphs and digraphs |
scientific article |
Statements
Disjoint cycles of different lengths in graphs and digraphs (English)
0 references
12 December 2017
0 references
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.
0 references
vertex-disjoint cycles
0 references
different lengths
0 references
minimum degree
0 references
0 references