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 language||English (US)|
|Number of pages||7|
|Journal||Journal of Graph Theory|
|State||Published - Jul 1996|
All Science Journal Classification (ASJC) codes
- Geometry and Topology