Edge-Disjoint Cycles in Regular Directed Graphs

Noga Alon; Colin McDiarmid; Michael Molloy

doi:10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N

Edge-Disjoint Cycles in Regular Directed Graphs

Noga Alon, Colin McDiarmid, Michael Molloy

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	231-237
Number of pages	7
Journal	Journal of Graph Theory
Volume	22
Issue number	3
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N
State	Published - Jul 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Access to Document

10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N

Cite this

@article{62122dee3b8e450ca078c267214d3e29,

title = "Edge-Disjoint Cycles in Regular Directed Graphs",

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.",

author = "Noga Alon and Colin McDiarmid and Michael Molloy",

year = "1996",

month = jul,

doi = "10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N",

language = "English (US)",

volume = "22",

pages = "231--237",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Edge-Disjoint Cycles in Regular Directed Graphs

AU - Alon, Noga

AU - McDiarmid, Colin

AU - Molloy, Michael

PY - 1996/7

Y1 - 1996/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030545939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030545939&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N

DO - 10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.0.CO;2-N

M3 - Article

AN - SCOPUS:0030545939

SN - 0364-9024

VL - 22

SP - 231

EP - 237

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Edge-Disjoint Cycles in Regular Directed Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this