Premium
Long paths and cycles in random subgraphs of graphs with large minimum degree
Author(s) -
Krivelevich Michael,
Lee Choongbum,
Sudakov Benny
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20508
Subject(s) - mathematics , combinatorics , random graph , degree (music) , random regular graph , path (computing) , discrete mathematics , binomial (polynomial) , graph , graph factorization , graph power , line graph , 1 planar graph , statistics , computer science , physics , acoustics , programming language
For a given finite graph G of minimum degree at least k , let G p be a random subgraph of G obtained by taking each edge independently with probability p . We prove that (i) if p ≥ ω / k for a function ω = ω ( k ) that tends to infinity as k does, then G p asymptotically almost surely contains a cycle (and thus a path) of length at least ( 1 − o ( 1 ) ) k , and (ii) if p ≥ ( 1 + o ( 1 ) ) ln k / k , then G p asymptotically almost surely contains a path of length at least k . Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015