Cover time of a random graph with given degree sequence (Q456654)

The authors study the cover time of a graph chosen uniformly at random from the set of \(n\)-vertex graphs with a given degree sequence \(\mathbf{d}\). They obtain an asymptoticly exact result which holds with high probability (as \(n\rightarrow\infty\)) for degree sequences \(\mathbf{d}\) satisfying certain restrictions, most notable of them that the average degree is \(o(\sqrt{\log n})\). More precisely, they prove that under these conditions, the cover time of a typical random graph with degree sequence \(\mathbf{d}\) is asymptotically \(\frac{d-1}{d-2}\frac{\theta}{d}n\log n\). Here, \(\theta\) is the average degree, and \(d\) is the ``effective minimum degree'' of \(\mathbf{d}\), i.e., the smallest \(d\) such that \(G\) contains a vanishing proportion of vertices of degrees \(d-1,d-2,\dots\).