Paths and cycles in random subgraphs of graphs with large minimum degree (Q1753122): Difference between revisions

Summary: For a graph \(G\) and \(p\in [0,1]\), let \(G_p\) arise from \(G\) by deleting every edge mutually independently with probability \(1-p\). The random graph model \((K_n)_p\) is certainly the most investigated random graph model and also known as the \(G(n,p)\)-model. We show that several results concerning the length of the longest path/cycle naturally translate to \(G_p\) if \(G\) is an arbitrary graph of minimum degree at least \(n-1\). For a constant \(c>0\) and \(p=\frac{c}{n}\), we show that asymptotically almost surely the length of the longest path in \(G_p\) is at least \((1-(1+\epsilon(c))ce^{-c})n\) for some function \(\epsilon(c)\rightarrow 0\) as \(c\rightarrow \infty\), and the length of the longest cycle is a least \((1-O(c^{- \frac{1}{5}}))n\). The first result is asymptotically best-possible. This extends several known results on the length of the longest path/cycle of a random graph in the \(G(n,p)\)-model to the random graph model \(G_p\) where \(G\) is a graph of minimum degree at least \(n-1\).