Pancyclic subgraphs of random graphs (Q2911059)

The authors study pancyclic subgraphs of classical random graph \(G(n,p)\). A graph of order \(n\) is called pancyclic if it contains a cycle of length \(t\) for all \(3\leq t\leq n\). It is shown that, if \(p\geq n^{-1/2}\), then a.a.s. every Hamiltonian subgraph \(G'\) of \(G(n,p)\) with more than \((\frac12+o(1))n^2p/2\) edges is pancyclic. The proof heavily relies on the fact that \(G'\) contains a Hamilton cycle. The prefactor \(1/2\) is shown to be optimal.