Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

Allan Lo; Viresh Patel; Mehmet Akif  Yildiz

doi:10.1017/fms.2025.28

Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

Allan Lo
, Viresh Patel
, Mehmet Akif Yildiz^*

^*Corresponding author for this work

Mathematics

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

40 Downloads (Pure)

Abstract

A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with n≤4d+1 is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all α>0, there exists n0=n0(α) such that every d-regular digraph on n≥n0 vertices with d≥αn can be covered by at most n/(d+1) vertex-disjoint cycles, and moreover that if G is an oriented graph, then at most n/(2d+1) cycles suffice.

Original language	English
Article number	e79
Number of pages	31
Journal	Forum of Mathematics, Sigma
Volume	13
DOIs	https://doi.org/10.1017/fms.2025.28
Publication status	Published - 28 Apr 2025

Access to Document

10.1017/fms.2025.28Licence: Creative Commons: Attribution (CC BY)

LoA2025CycleFinal published version, 600 KBLicence: Creative Commons: Attribution (CC BY)

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

Cycle Partition of Dense Regular Digraphs and Oriented Graphs
Lo, A. (Advisor)
21 Jun 2024
Activity: Academic and Industrial events › Guest lecture or Invited talk

Cite this

@article{7e536938226d40b99fe4f6c7fc2b3512,

title = "Cycle Partitions in Dense Regular Digraphs and Oriented Graphs",

abstract = "A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with n≤4d+1 is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all α>0, there exists n0=n0(α) such that every d-regular digraph on n≥n0 vertices with d≥αn can be covered by at most n/(d+1) vertex-disjoint cycles, and moreover that if G is an oriented graph, then at most n/(2d+1) cycles suffice.",

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

year = "2025",

month = apr,

day = "28",

doi = "10.1017/fms.2025.28",

language = "English",

volume = "13",

journal = "Forum of Mathematics, Sigma",

issn = "2050-5094",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

AU - Lo, Allan

AU - Patel, Viresh

AU - Yildiz, Mehmet Akif

PY - 2025/4/28

Y1 - 2025/4/28

N2 - A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with n≤4d+1 is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all α>0, there exists n0=n0(α) such that every d-regular digraph on n≥n0 vertices with d≥αn can be covered by at most n/(d+1) vertex-disjoint cycles, and moreover that if G is an oriented graph, then at most n/(2d+1) cycles suffice.

AB - A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with n≤4d+1 is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all α>0, there exists n0=n0(α) such that every d-regular digraph on n≥n0 vertices with d≥αn can be covered by at most n/(d+1) vertex-disjoint cycles, and moreover that if G is an oriented graph, then at most n/(2d+1) cycles suffice.

UR - https://arxiv.org/pdf/2309.11677

U2 - 10.1017/fms.2025.28

DO - 10.1017/fms.2025.28

M3 - Article

SN - 2050-5094

VL - 13

JO - Forum of Mathematics, Sigma

JF - Forum of Mathematics, Sigma

M1 - e79

ER -

Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

Abstract

Access to Document

Fingerprint

Projects

Ramsey theory: an extremal perspective

Matchings and tilings in graphs

Activities

Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Cite this