Research Library

Premium Longest cycles in sparse random digraphs
Author(s)
Krivelevich Michael,
Lubetzky Eyal,
Sudakov Benny
Publication year2013
Publication title
random structures and algorithms
Resource typeJournals
PublisherWiley Subscription Services
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 (2 e − c − o (1)) n vertices with zero in‐degree or out‐degree. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013
Subject(s)acoustics , combinatorics , degree (music) , digraph , graph , mathematical analysis , mathematics , physics , random graph , upper and lower bounds
Language(s)English
SCImago Journal Rank1.314
H-Index69
eISSN1098-2418
pISSN1042-9832
DOI10.1002/rsa.20435

This content is not available in your region!

Continue researching here.