PreprintarXiv licencearXiv
New results on openly disjoint cycles in regular digraphs
Abstract
Given a digraph D, let c(D) be the largest size of a collection of openly disjoint directed cycles through a common vertex, and let cr be the minimum of c(D) over all r-regular digraphs D. In 2005, Seymour asked whether every r-regular digraph satisfies c(D)=r. Mader answered Seymour's problem negatively for every r≥ 8, but conjectured that nevertheless limr→∞cr=∞. Recently, Steiner confirmed this conjecture by proving ⌈ 3r/22⌉ ≤ cr ≤ 7⌈ r/8⌉. In this paper, we first answer Seymour's problem negatively for r∈ {6,7}, and then improve Steiner's bound to ⌈ r/6⌉ ≤ cr ≤ 5⌈ r/6⌉.
Related
- Arc-disjoint Hamiltonian paths in Cayley digraphs with a normal difference subgroup
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
- A quadratic refinement of Jackson's \CE\ condition for Hamilton cycles in digraphs
- A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs
- Large corank of dense random regular digraphs
BibTeX
@misc{chen2026results,
title = {{New results on openly disjoint cycles in regular digraphs}},
author = {Bin Chen and Wenshen Wu and Meishaung Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41372},
eprint = {2610.41372},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41372},
}
RIS
TY - UNPB
TI - New results on openly disjoint cycles in regular digraphs
AU - Bin Chen
AU - Wenshen Wu
AU - Meishaung Chen
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41372
UR - https://arxiv.org/abs/2610.41372
AB - Given a digraph D, let c(D) be the largest size of a collection of openly disjoint directed cycles through a common vertex, and let c_r be the minimum of c(D) over all r-regular digraphs D. In 2005, Seymour asked whether every r-regular digraph satisfies c(D)=r. Mader answered Seymour's problem negatively for every r≥ 8, but conjectured that nevertheless lim_r→∞c_r=∞. Recently, Steiner confirmed this conjecture by proving ⌈ 3r/22⌉ ≤ c_r ≤ 7⌈ r/8⌉. In this paper, we first answer Seymour's problem negatively for r∈ {6,7}, and then improve Steiner's bound to ⌈ r/6⌉ ≤ c_r ≤ 5⌈ r/6⌉.
ER -