Skip to Main content Skip to Navigation
Conference papers

Cover time of a random graph with given degree sequence

Abstract : In this paper we establish the cover time of a random graph $G(\textbf{d})$ chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}$. We show that under certain restrictions on $\textbf{d}$, the cover time of $G(\textbf{d})$ is with high probability asymptotic to $\frac{d-1}{ d-2} \frac{\theta}{ d}n \log n$. Here $\theta$ is the average degree and $d$ is the $\textit{effective minimum degree}$. The effective minimum degree is the first entry in the sorted degree sequence which occurs order $n$ times.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:34:10 PM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:04:29 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01185603, version 1



Mohammed Abdullah, Colin Cooper, Alan Frieze. Cover time of a random graph with given degree sequence. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.1-20. ⟨hal-01185603⟩



Record views


Files downloads