Cycle Partitions in Dense Regular Digraphs and Oriented Graphs
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2025-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509425000283/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849310454604627968 |
|---|---|
| author | Allan Lo Viresh Patel Mehmet Akif Yıldız |
| author_facet | Allan Lo Viresh Patel Mehmet Akif Yıldız |
| author_sort | Allan Lo |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-d5ef0aebfc4a4c168a9a5aba4e780402 |
| institution | Kabale University |
| issn | 2050-5094 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj-art-d5ef0aebfc4a4c168a9a5aba4e7804022025-08-20T03:53:43ZengCambridge University PressForum of Mathematics, Sigma2050-50942025-01-011310.1017/fms.2025.28Cycle Partitions in Dense Regular Digraphs and Oriented GraphsAllan Lo0https://orcid.org/0000-0001-9767-2863Viresh Patel1Mehmet Akif Yıldız2https://orcid.org/0000-0002-3349-9165School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom; E-mail:School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London, E1 4NS, United Kingdom; E-mail:Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam, Science Park 107, Amsterdam, 1098XG, The NetherlandsA 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.https://www.cambridge.org/core/product/identifier/S2050509425000283/type/journal_article05C3505C2005C45 |
| spellingShingle | Allan Lo Viresh Patel Mehmet Akif Yıldız Cycle Partitions in Dense Regular Digraphs and Oriented Graphs Forum of Mathematics, Sigma 05C35 05C20 05C45 |
| title | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| title_full | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| title_fullStr | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| title_full_unstemmed | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| title_short | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| title_sort | cycle partitions in dense regular digraphs and oriented graphs |
| topic | 05C35 05C20 05C45 |
| url | https://www.cambridge.org/core/product/identifier/S2050509425000283/type/journal_article |
| work_keys_str_mv | AT allanlo cyclepartitionsindenseregulardigraphsandorientedgraphs AT vireshpatel cyclepartitionsindenseregulardigraphsandorientedgraphs AT mehmetakifyıldız cyclepartitionsindenseregulardigraphsandorientedgraphs |