×

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
PDF BibTeX XML Cite
Full Text: Link arXiv