Collecting coupons on trees,and the cover time of random walks

We consider the cover timeE _u G], the expected time it takes a random walk that starts at vertexu to visit alln vertices of a connected graphG. Aleliunas et al introduced the spanning tree argument: for any spanning treeT of the graphG, E _u G]≤WT], whereWT] is the sum of commute times along the edges ofT. By refining the spanning tree argument we obtain: $$E_u G] \leqslant \frac{1}{2}(\mathop {\min }\limits_T WT]] + \mathop {\max }\limits_{\upsilon \in G} Hu,\upsilon ] - H\upsilon ,u]])$$ whereHu,v] is the hitting time fromu tov. We use this bound to show:

1. max _G min _u E _u G]=(1+o(1))2n ³/27. This answers an open question of Aldous.
2. Then-path is then-vertex tree on which the cover time is maximized. This confirms a conjecture of Brightwell and Winkler.
3. For regular graphs,E _u G]<2n ². This improves the leading constant in previously known upper bounds.

We also provide upper bounds onE _u ⁺ G], the expected time to coverG and return tou.