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 Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:34:10 PM
Last modification on : Saturday, June 25, 2022 - 11:08:57 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:04:29 AM


Publisher files allowed on an open archive




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, ⟨10.46298/dmtcs.2804⟩. ⟨hal-01185603⟩



Record views


Files downloads