file.pdf (631.61 kB)
0/0

Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Download (631.61 kB)
journal contribution
posted on 01.05.2014 by Colin Cooper, Alan Frieze, Eyal Lubetzky

We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set [n] and degree sequence d = (di) n i=1. In a previous work [1], the asymptotic cover time was obtained under a number of assumptions on d, the most significant being that di ≥ 3 for all i. Here we replace this assumption by di ≥ 2. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of G(n, p).

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/rsa.20573

Date

01/05/2014

Exports

Exports