Edge-Disjoint Cycles in Regular Directed Graphs

Noga Alon, Colin McDiarmid, Michael Molloy

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

We prove that any k-regular directed graph with no parallel edges contains a collection of at least Ω(k2) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least (k+12) disjoint cycles, and note that this holds for k ≤ 3.

Original languageEnglish (US)
Pages (from-to)231-237
Number of pages7
JournalJournal of Graph Theory
Volume22
Issue number3
DOIs
StatePublished - Jul 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Edge-Disjoint Cycles in Regular Directed Graphs'. Together they form a unique fingerprint.

Cite this