## Abstract

Long paths and cycles in sparse random graphs and digraphs were studied intensively in the 1980's. It was finally shown by Frieze in 1986 that the random graph \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{G}}(n,p)$\end{document} with p = c/n has a cycle on at all but at most (1 + ε)ce^{-c}n vertices with high probability, where ε = ε (c) → 0 as c → ∞. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n,p)$\end{document} no tight result was known and the best estimate was a factor of c/2 away from the corresponding lower bound. In this work we close this gap and show that the random digraph \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal{D}}(n,p)$\end{document} with p = c/n has a cycle containing all but (2 + ε)e^{-c}n vertices w.h.p., where ε = ε (c) → 0 as c → ∞. This is essentially tight since w.h.p. such a random digraph contains (2e^{-c} - o(1))n vertices with zero in-degree or out-degree.

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

Pages (from-to) | 1-15 |

Number of pages | 15 |

Journal | Random Structures and Algorithms |

Volume | 43 |

Issue number | 1 |

DOIs | |

State | Published - Aug 2013 |

## Keywords

- Cycles
- Directed graphs
- Random graphs

## ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics