Forum of Mathematics, Sigma (Jan 2025)

Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

  • Allan Lo,
  • Viresh Patel,
  • Mehmet Akif Yıldız

DOI
https://doi.org/10.1017/fms.2025.28
Journal volume & issue
Vol. 13

Abstract

Read online

A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with $n\leq 4d+1$ is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all $\alpha>0$ , there exists $n_0=n_0(\alpha )$ such that every d-regular digraph on $n\geq n_0$ vertices with $d \ge \alpha 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.

Keywords