An improved bound for disjoint directed cycles

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We show that every directed graph with minimum out-degree at least 18k contains at least k vertex disjoint cycles. This is an improvement over the result of Alon who showed this result for digraphs of minimum out-degree at least 64k. The main benefit of the argument is that getting better results for small values of k allows for further improvements to the constant.

Original languageEnglish (US)
Pages (from-to)2231-2236
Number of pages6
JournalDiscrete Mathematics
Volume341
Issue number8
DOIs
StatePublished - Aug 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Directed graph
  • Disjoint cycles
  • Minimal out-degree

Fingerprint

Dive into the research topics of 'An improved bound for disjoint directed cycles'. Together they form a unique fingerprint.

Cite this