On oriented cycles in randomly perturbed digraphs
Preprint
Abstract
In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Spanning cycles in random directed graphsRandom Structures & Algorithms, 2024
- 2-universality in randomly perturbed graphsEuropean Journal of Combinatorics, 2020
- Spanning trees in random graphsAdvances in Mathematics, 2019
- Spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Universality for bounded degree spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Packing and counting arbitrary Hamilton cycles in random digraphsRandom Structures & Algorithms, 2018
- The size Ramsey number of a directed pathJournal of Combinatorial Theory, Series B, 2012
- How many random edges make a dense graph hamiltonian?Random Structures & Algorithms, 2002
- Oriented hamilton cycles in digraphsJournal of Graph Theory, 1995
- Pancyclic graphs IJournal of Combinatorial Theory, Series B, 1971