Vertex-disjoint cycles in tournaments
Maoqun Wang, Weihua Yang
Abstract
Open-access reader
Maoqun Wang, Weihua Yang
Abstract
Open-access reader
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.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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