Premium
The cover time of the giant component of a random graph
Author(s) -
Cooper Colin,
Frieze Alan
Publication year - 2008
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.20201
Subject(s) - cover (algebra) , random walk , monotone polygon , combinatorics , mathematics , graph , random graph , component (thermodynamics) , struct , giant component , discrete mathematics , statistics , computer science , physics , geometry , thermodynamics , engineering , mechanical engineering , programming language
We study the cover time of a random walk on the largest component of the random graph G n , p . We determine its value up to a factor 1 + o (1) whenever n p = c > 1, c = O (ln n ). In particular, we show that the cover time is not monotone for c = Θ (ln n ). We also determine the cover time of the k ‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008