On the cover time of dense graphs

Abstract

We consider arbitrary graphs $G$ with $n$ vertices and minimum degree at least $\delta n$ where $\delta >0$ is constant. If the conductance of $G$ is sufficiently large then we obtain an asymptotic expression for the cover time $C_G$ of $G$ as the solution to an explicit transcendental equation. Failing this, if the mixing time of a random walk on $G$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense sub-graphs with high conductance. Failing this we give a deterministic asymptotic (2+o(1))-approximation of $C_G$.

References in corpus (1)

• A polynomial time approximation scheme for computing the supremum of Gaussian processes