# The Cover Time of Random Walks on Random Graphs

 COMPUTER SCIENCE/DISCRETE MATH I Topic: The Cover Time of Random Walks on Random Graphs Speaker: Alan Frieze Affiliation: Carnegie Mellon University Date: Monday, March 27 Time/Room: 11:15am - 12:15pm/S-101

We give asymptotically precise estimates for the expected time taken for a random walk to visit all vertices of a graph, viz. the cover time. We do this for several models of random graphs viz. $G_{n,p}$ when $p$ is above the connectivity threshold; random $r$-regular graphs; the giant component of $G_{n,p)$ when the average degree is a constant larger than 1; the preferential attachment graph. The results are based on a lemma that can most usefully be applied to graphs of "high girth" and for which the random walk is "rapidly mixing" e.g. Ramanujan graphs.