Extremal cover times for random walks on trees

Let C ν ( T ) denote the “cover time” of the tree T from the vertex v , that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C ν ( T ) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2 n In n ) by showing that C ν ( T ) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).