| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [10 references]
https://hal.inria.fr/hal-01185603
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
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
File
dmAM0101.pdf
Publisher files allowed on an open archive