COLLECTING COUPONS ON TREES, AND THE COVER TIME OF RANDOM-WALKS

We consider the cover time E-u[G], the expected time it takes a random walk that starts at vertex u to visit all n vertices of a connected g raph G. Aleliunas et al introduced the spanning tree argument: for any spanning tree T of the graph G, E-u[G] less than or equal to W[T], wh ere W[T] is the sum of commute times along the edges of T. By refining the spanning tree argument we obtain: E-u[G]less than or equal to 1/2 (min(T)[W[T]]+max(v is an element of G)[H[u, v] - H[v, u]]) where H[u, v] is the hitting time from u to v. We use this bound to show: 1. max( G) min(u) E-u[G] = (1 + o(1))2n(3)/27. This answers an open question o f Aldous. 2. The n-path is the n-vertex tree on which the cover time i s maximized. This confirms a conjecture of Brightwell and Winkler. 3. For regular graphs, E-u[G] < 2n(2). This improves the leading constant in previously known upper bounds. We also provide upper bounds on E-u (+)[G], the expected time to cover G and return to u.