Long paths and cycles in random subgraphs of graphs with large minimum degree

الأصل · EN

For a graph G and p∈ [0,1], let Gₚ arise from G by deleting every edge mutually independently with probability 1-p. The random graph model (Kₙ)ₚ 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ₚ if G is an arbitrary graph of minimum degree at least n-1. For a constant c, we show that asymptotically almost surely the length of the longest path is at least (1-(1+ε(c))ce⁻ᶜ)n for some function ε(c)→ 0 as c→ ∞, and the length of the longest cycle is a least (1-O(c⁻ ¹/⁵))n. The first result is asymptotically best-possible. This extents several known results on the length of the longest path/cycle of a random graph in the G(n,p)-model.