Two disjoint cycles in digraphs

2022/05/22 by Mikołaj Lewandowski, Lewandowski, Mikołaj, Joanna Polcyn +3
Computer Science · Engineering · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2205.10826

openalex publication_date 2022/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Bermond and Thomassen conjectured that every digraph with minimum outdegree at least 2k-1 contains k vertex disjoint cycles. So far the conjecture was verified for k≤ 3. Here we generalise the question asking for all outdegree sequences which force k vertex disjoint cycles and give the full answer for k≤ 2.

Related

• On the number of vertex-disjoint cycles in digraphs
• Vertex-disjoint cycles in tournaments
• Note on Disjoint Cycles in Multipartite Tournaments
• Vertex-disjoint cycles of different lengths in tournaments
• Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree