Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

Allan Lo, Viresh Patel, Mehmet Akif Yildiz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
JournalForum of Mathematics, Sigma
Publication statusAccepted/In press - 21 Dec 2024

Bibliographical note

Not yet published as of 10/02/2025

Fingerprint

Dive into the research topics of 'Cycle Partitions in Dense Regular Digraphs and Oriented Graphs'. Together they form a unique fingerprint.

Cite this