Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Allan Lo; Viresh Patel; Mehmet Akif  Yildiz

doi:10.5817/CZ.MUNI.EUROCOMB23-099

Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Allan Lo, Viresh Patel, Mehmet Akif Yildiz

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

35 Downloads (Pure)

Abstract

Magnant and Martin [24] conjectured that every d-regular graph on n vertices can be covered by n/(d + 1) vertex-disjoint paths. Gruslys and Letzter [11] verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all α > 0, there exists n₀ = n₀(α) such that every d-regular digraph on n vertices with d ≥ αn can be covered by at most n/(d + 1) vertex-disjoint cycles. Moreover if G is an oriented graph, then n/(2d + 1) cycles suffice. This also establishes Jackson’s long standing conjecture [14] for large n that every d-regular oriented graph on n vertices with n ≤ 4d + 1 is Hamiltonian.

Original language	English
Title of host publication	EUROCOMB’23
Publisher	Masaryk University Press
Pages	1-8
Number of pages	8
DOIs	https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-099
Publication status	Published - 28 Aug 2023
Event	European Conference on Combinatorics, Graph Theory and Applications - Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic Duration: 28 Aug 2023 → 1 Sept 2023 https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Publication series

Name	European Conference on Combinatorics, Graph Theory and Applications
Publisher	Masaryk University Press
Number	12
ISSN (Electronic)	2788-3116

Conference

Conference	European Conference on Combinatorics, Graph Theory and Applications
Abbreviated title	EUROCOMB'23
Country/Territory	Czech Republic
City	Prague
Period	28/08/23 → 1/09/23
Internet address	https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Access to Document

10.5817/CZ.MUNI.EUROCOMB23-099Licence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

LoA2023CycleFinal published version, 406 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Ramsey theory: an extremal perspective
Treglown, A. (Co-Investigator) & Lo, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/01/22 → 31/12/24
Project: Research Councils
Matchings and tilings in graphs
Lo, A. (Co-Investigator) & Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@inproceedings{a7e29db5f6aa4cc78a4d547209dd8ba0,

title = "Cycle Partition of Dense Regular Digraphs and Oriented Graphs",

abstract = "Magnant and Martin [24] conjectured that every d-regular graph on n vertices can be covered by n/(d + 1) vertex-disjoint paths. Gruslys and Letzter [11] verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all α > 0, there exists n0 = n0(α) such that every d-regular digraph on n vertices with d ≥ αn can be covered by at most n/(d + 1) vertex-disjoint cycles. Moreover if G is an oriented graph, then n/(2d + 1) cycles suffice. This also establishes Jackson{\textquoteright}s long standing conjecture [14] for large n that every d-regular oriented graph on n vertices with n ≤ 4d + 1 is Hamiltonian. ",

author = "Allan Lo and Viresh Patel and Yildiz, {Mehmet Akif}",

year = "2023",

month = aug,

day = "28",

doi = "10.5817/CZ.MUNI.EUROCOMB23-099",

language = "English",

series = "European Conference on Combinatorics, Graph Theory and Applications",

publisher = "Masaryk University Press",

number = "12",

pages = "1--8",

booktitle = "EUROCOMB{\textquoteright}23",

note = "European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 ; Conference date: 28-08-2023 Through 01-09-2023",

url = "https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/",

}

Lo, A, Patel, V & Yildiz, MA 2023, Cycle Partition of Dense Regular Digraphs and Oriented Graphs. in EUROCOMB’23., 99, European Conference on Combinatorics, Graph Theory and Applications, no. 12, Masaryk University Press, pp. 1-8, European Conference on Combinatorics, Graph Theory and Applications, Prague, Czech Republic, 28/08/23. https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-099

TY - GEN

T1 - Cycle Partition of Dense Regular Digraphs and Oriented Graphs

AU - Lo, Allan

AU - Patel, Viresh

AU - Yildiz, Mehmet Akif

PY - 2023/8/28

Y1 - 2023/8/28

N2 - Magnant and Martin [24] conjectured that every d-regular graph on n vertices can be covered by n/(d + 1) vertex-disjoint paths. Gruslys and Letzter [11] verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all α > 0, there exists n0 = n0(α) such that every d-regular digraph on n vertices with d ≥ αn can be covered by at most n/(d + 1) vertex-disjoint cycles. Moreover if G is an oriented graph, then n/(2d + 1) cycles suffice. This also establishes Jackson’s long standing conjecture [14] for large n that every d-regular oriented graph on n vertices with n ≤ 4d + 1 is Hamiltonian.

AB - Magnant and Martin [24] conjectured that every d-regular graph on n vertices can be covered by n/(d + 1) vertex-disjoint paths. Gruslys and Letzter [11] verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all α > 0, there exists n0 = n0(α) such that every d-regular digraph on n vertices with d ≥ αn can be covered by at most n/(d + 1) vertex-disjoint cycles. Moreover if G is an oriented graph, then n/(2d + 1) cycles suffice. This also establishes Jackson’s long standing conjecture [14] for large n that every d-regular oriented graph on n vertices with n ≤ 4d + 1 is Hamiltonian.

U2 - 10.5817/CZ.MUNI.EUROCOMB23-099

DO - 10.5817/CZ.MUNI.EUROCOMB23-099

M3 - Conference contribution

T3 - European Conference on Combinatorics, Graph Theory and Applications

SP - 1

EP - 8

BT - EUROCOMB’23

PB - Masaryk University Press

T2 - European Conference on Combinatorics, Graph Theory and Applications

Y2 - 28 August 2023 through 1 September 2023

ER -

Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Ramsey theory: an extremal perspective

Matchings and tilings in graphs

Cite this