## Abstract

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every α > 0, there exists a constant C such that for every n-vertex digraph of minimum semi-degree at least á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.

Original language | English (US) |
---|---|

Journal | Combinatorics Probability and Computing |

DOIs | |

State | Accepted/In press - 2023 |

## Keywords

- absorbing method
- cycles
- directed graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics