Cover time of a random graph with given degree sequence
Mohammed Abdullah, Colin Cooper, Alan Frieze
Abstract
In this paper we establish the cover time of a random graph G(d) chosen uniformly at random from the set of graphs with vertex set [n] and degree sequence d. We show that under certain restrictions on d, the cover time of G(d) is with high probability asymptotic to d-1 / d-2θ / dnlogn. Here θ is the average degree and d is the effective minimum degree. The effective minimum degree is the first entry in the sorted degree sequence which occurs order n times.
Full Text: PostScript PDF