pipette
ENEnglish

A near-linear Chv\'atal--Erd\H{o}s condition for Hamilton cycles in digraphs

Chengli Li, Bo Ning

Preprint

En palabras de los autores

For a digraph , let be the largest size of a vertex set containing no directed -cycle. Let be the least positive integer such that every -strongly connected digraph with has a Hamilton cycle. Jackson and Ordaz conjectured that . Towards this conjecture, we establish the near-linear bound and hence for every fixed . We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph with contains a directed cycle of every length from to .

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.