2020arXiv (Cornell University)Open access

Disjoint cycles with length constraints in digraphs of large connectivity or minimum degree

Raphael Steiner

Open full text 0 citations

Abstract

A conjecture by Lichiardopol states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $k \in \mathbb{N}$, there exists $s(k) \in \mathbb{N}$ such that every strongly $s(k)$-connected digraph contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every $k \in \mathbb{N}$ we construct a strongly $k$-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out- and in-degree at least $K$ contains $3$ vertex-disjoint directed cycles of pairwise distinct lengths.

Open-access reader

About this research paper

What this paper is about

A conjecture by Lichiardopol states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $k \in \mathbb{N}$, there exists $s(k) \in \mathbb{N}$ such that every strongly $s(k)$-connected digraph contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every $k \in \mathbb{N}$ we construct a strongly $k$-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out- and in-degree at least $K$ contains $3$ vertex-disjoint directed cycles of pairwise distinct lengths.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A conjecture by Lichiardopol states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $k \in \mathbb{N}$, there exists $s(k) \in \mathbb{N}$ such that every strongly $s(k)$-connected digraph contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every $k \in \mathbb{N}$ we construct a strongly $k$-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out- and in-degree at least $K$ contains $3$ vertex-disjoint directed cycles of pairwise distinct lengths.

Key concepts: Digraph, Combinatorics, Disjoint sets, Mathematics, Conjecture, Vertex (graph theory), Degree (music), Integer (computer science)

Related papers

Back to paper searchBrowse research topicsOriginal source
Disjoint cycles with length constraints in digraphs of large connectivity or minimum degree — Research Paper | ScholarLens