The cover time of the giant component of a random graph |
| |
| Authors: | Colin Cooper Alan Frieze |
| |
| Affiliation: | 1. Department of Computer Science, King's College, University of London, London WC2R 2LS, UK;2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213 |
| |
| Abstract: | We study the cover time of a random walk on the largest component of the random graph Gn,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
| Keywords: | cover time random graphs giant component |
|
|
