An improved bound for disjoint directed cycles

Matija Bucić

doi:10.1016/j.disc.2018.04.027

An improved bound for disjoint directed cycles

Matija Bucić

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

12 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 language	English (US)
Pages (from-to)	2231-2236
Number of pages	6
Journal	Discrete Mathematics
Volume	341
Issue number	8
DOIs	https://doi.org/10.1016/j.disc.2018.04.027
State	Published - Aug 2018
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Directed graph
Disjoint cycles
Minimal out-degree

Access to Document

10.1016/j.disc.2018.04.027

Cite this

@article{08fb26b6961b4977a26a827a65c99d3e,

title = "An improved bound for disjoint directed cycles",

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

keywords = "Directed graph, Disjoint cycles, Minimal out-degree",

author = "Matija Buci{\'c}",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = aug,

doi = "10.1016/j.disc.2018.04.027",

language = "English (US)",

volume = "341",

pages = "2231--2236",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - An improved bound for disjoint directed cycles

AU - Bucić, Matija

PY - 2018/8

Y1 - 2018/8

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

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

KW - Directed graph

KW - Disjoint cycles

KW - Minimal out-degree

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

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

U2 - 10.1016/j.disc.2018.04.027

DO - 10.1016/j.disc.2018.04.027

M3 - Article

AN - SCOPUS:85047081989

SN - 0012-365X

VL - 341

SP - 2231

EP - 2236

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 8

ER -

An improved bound for disjoint directed cycles

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this