![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo ARXIV 1606.07639 Source : ScholeXplorer IsRelatedTo DOI 10.1214/17-aap1289 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1606.07639 Source : ScholeXplorer IsRelatedTo HANDLE 1887/69366
|