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

2015/10/30 by Stefan Ehard, Felix Joos, Ehard, Stefan +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1510.09166

13 pages

arxiv created 2015/12/15 · arxiv updated 2015/12/16

Abstract

For a graph G and p∈ [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, we show that asymptotically almost surely the length of the longest path is at least (1-(1+ε(c))ce^-c)n for some function ε(c)→ 0 as c→ ∞, and the length of the longest cycle is a least (1-O(c^{- (1)/(5)}))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.

Related

• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Long paths and cycles in random subgraphs of H-free graphs
• A scaling limit for the length of the longest cycle in a sparse random\n graph
• Cycle lengths in sparse random graphs
• Longest cycles in sparse random digraphs