Premium
The cover time of sparse random graphs
Author(s) -
Cooper Colin,
Frieze Alan
Publication year - 2006
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.20151
Subject(s) - cover (algebra) , struct , combinatorics , mathematics , random graph , binary logarithm , random walk , discrete mathematics , statistics , computer science , graph , engineering , mechanical engineering , programming language
We study the cover time of a random walk on graphs G ∈ G n , p when $p={c\log n \over n}, c>1$ . We prove that whp , the cover time, is asymptotic to $c\log({c \over c-1})n\log n$ . © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007