Cycles in random graphs (Q1185100)

The paper considers random graphs \(G(n,p)\) with \(n\) vertices in which each possible edge is presented independently with probability \(p=p(n)\). The paper shows that, asymptotically, such graphs are very nearly pancyclic. More precisely it is shown that, if \(\varepsilon>0\) and \(np(n)\to\infty\), then the probability that \(G(n,p)\) contains cycles of each length from 3 to \(n-(1+\varepsilon)v^ 1(n,p)\), tends to 1 as \(n\to\infty\) (where \(v^ 1(n,p)\) denotes the number of vertices of degree 1 in \(G(n,p))\).