Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Abstract

We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\mathbf{d}=(d_i{)}_{i=1}^n$. In a previous work, the asymptotic cover time was obtained under a number of assumptions on $\mathbf{d}$, the most significant being that $d_i\ge 3$ for all $i$. Here we replace this assumption by $d_i\ge 2$. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of $\mathcal{G}(n,p)$.

arXiv comment48 pages