### 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