On the cover time for random walks on random graphs

The cover time, C, for a simple random walk on a realization, G(N), of G(N, p), the random graph on N vertices where each two vertices have an edge between them with probability p independently, is studied. The parameter p is allowed to decrease with N and p is written on the Form f(N)/N, where it is assumed that f(N) greater than or equal to c log N for some c > 1 to asymptotically ensure connectedness of the graph. It is shown that if f(N) is of higher order than log N, then, with probability 1 - o(1), (1 - epsilon)N log N less than or equal to E[C\G(N)] less than or equal to (1 + epsilon)N log N for any fixed epsilon > 0, whereas if f(N) = O(log N), there exists a constant a > 0 such that, with probability 1 - o(1), E[C\G(N)] greater than or equal to (1 + a)N log N. It is furthermore shown that if f(N) is of higher order than (log N)(3) then Var(C\G(N)) = o((N log N)(2)) with probability 1 - o(1), so that with probability 1 - o(1) the stronger statement that (1 - epsilon)N log N less than or equal to C less than or equal to (1 + epsilon)N log N holds.