Cycle Partitions in Dense Regular Digraphs and Oriented Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909596157739008 |
|---|---|
| author | Lo, Allan Patel, Viresh Yıldız, Mehmet Akif |
| author_facet | Lo, Allan Patel, Viresh Yıldız, Mehmet Akif |
| contents | 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 $α>0$, there exists $n_0=n_0(α)$ such that every $d$-regular digraph on $n\geq n_0$ vertices with $d \geq α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 | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_11677 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs Lo, Allan Patel, Viresh Yıldız, Mehmet Akif Combinatorics 05C35, 05C38, 05C20, 05C70 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 $α>0$, there exists $n_0=n_0(α)$ such that every $d$-regular digraph on $n\geq n_0$ vertices with $d \geq α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. |
| title | Cycle Partitions in Dense Regular Digraphs and Oriented Graphs |
| topic | Combinatorics 05C35, 05C38, 05C20, 05C70 |
| url | https://arxiv.org/abs/2309.11677 |