PreprintarXiv licencearXiv
A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs
Abstract
For a digraph D, let α2(D) be the largest size of a vertex set containing no directed $2$-cycle. Let f2(a) be the least positive integer k such that every k-strongly connected digraph D with α2(D)≤ a has a Hamilton cycle. Jackson and Ordaz conjectured that f2(a)≤ a+1. Towards this conjecture, we establish the near-linear bound f2(a)=O ((a(log a)4)/((loglog a)2)), and hence f2(a)=Oε(a1+ε) for every fixed ε>0. We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph D with κ(D)≥α2(D)+1 contains a directed cycle of every length from $2$ to |V(D)|.
Related
- A quadratic refinement of Jackson's \CE\ condition for Hamilton cycles in digraphs
- A Chvátal--Erdős type condition for supereulerian digraphs with α2=4
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
- On Hamilton cycles in quasiprimitive graphs of order 2pq
- Alternating Hamilton Paths and Cycles in Poset Products
BibTeX
@misc{li2026nearlinear,
title = {{A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs}},
author = {Chengli Li and Bo Ning},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10292},
eprint = {2610.10292},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10292},
}
RIS
TY - UNPB
TI - A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs
AU - Chengli Li
AU - Bo Ning
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10292
UR - https://arxiv.org/abs/2610.10292
AB - For a digraph D, let α_2(D) be the largest size of a vertex set containing no directed $2$-cycle. Let f_2(a) be the least positive integer k such that every k-strongly connected digraph D with α_2(D)≤ a has a Hamilton cycle. Jackson and Ordaz conjectured that f_2(a)≤ a+1. Towards this conjecture, we establish the near-linear bound f_2(a)=O ((a(log a)^4)/((loglog a)^2)), and hence f_2(a)=O_ε(a^1+ε) for every fixed ε>0. We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph D with κ(D)≥α_2(D)+1 contains a directed cycle of every length from $2$ to |V(D)|.
ER -