2017arXiv (Cornell University)Open access

Vertex-disjoint cycles in tournaments

Maoqun Wang, Weihua Yang

Open full text 0 citations

Abstract

The Bermond-Thomassen conjecture states that, for any positive integer $r$, a digraph of minimum out-degree at least $2r-1$ contains at least $r$ vertex-disjoint directed cycles. Bessy, Sereni and Lichiardopol proved that a regular tournament $T$ of minimum degree $2r-1$ contains at least $r$ vertex-disjoint directed cycles, which shows that the above conjecture is true for tournaments. After that, Lichiardopol improved this result by showing that a $2r-1$-regular tournament contains at least $\frac{7}{6}r-\frac{7}{3}$ vertex-disjoint directed cycles. In this paper, we will extend the result to tournaments with minimum out-degree at least $2r-1$ by proving a more general result.

Open-access reader

About this research paper

What this paper is about

The Bermond-Thomassen conjecture states that, for any positive integer $r$, a digraph of minimum out-degree at least $2r-1$ contains at least $r$ vertex-disjoint directed cycles. Bessy, Sereni and Lichiardopol proved that a regular tournament $T$ of minimum degree $2r-1$ contains at least $r$ vertex-disjoint directed cycles, which shows that the above conjecture is true for tournaments. After that, Lichiardopol improved this result by showing that a $2r-1$-regular tournament contains at least $\frac{7}{6}r-\frac{7}{3}$ vertex-disjoint directed cycles. In this paper, we will extend the result to tournaments with minimum out-degree at least $2r-1$ by proving a more general result.

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

The Bermond-Thomassen conjecture states that, for any positive integer $r$, a digraph of minimum out-degree at least $2r-1$ contains at least $r$ vertex-disjoint directed cycles. Bessy, Sereni and Lichiardopol proved that a regular tournament $T$ of minimum degree $2r-1$ contains at least $r$ vertex-disjoint directed cycles, which shows that the above conjecture is true for tournaments. After that, Lichiardopol improved this result by showing that a $2r-1$-regular tournament contains at least $\frac{7}{6}r-\frac{7}{3}$ vertex-disjoint directed cycles. In this paper, we will extend the result to tournaments with minimum out-degree at least $2r-1$ by proving a more general result.

Key concepts: Vertex (graph theory), Disjoint sets, Combinatorics, Mathematics, Graph

Related papers

Back to paper searchBrowse research topicsOriginal source
Vertex-disjoint cycles in tournaments — Research Paper | ScholarLens