DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

Cover time of a random graph with given degree sequence

Mohammed Abdullah, Colin Cooper, Alan Frieze


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

Valid XHTML 1.0 Transitional