ON THE COVER TIME OF DENSE GRAPHS

We consider arbitrary graphs G with n vertices and minimum degree at least delta n where delta > 0 is constant. (a) 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. (b) If the conductance is not large enough to apply (a), but 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 subgraphs with high conductance. (c) If G fits neither (a) nor (b), then we give a deterministic asymptotic (2+o(1))-approximation of C-G.