Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G =( V ,  E ). Let C ( u ,  v ) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v , and let C ( G )=max u ,  v ∈ V C ( u ,  v ). Further, let ( n ,  m ) be the family of connected graphs on n vertices with m edges, $m\in\{n-1,\ldots,{n\choose2}\}$ , and let ( n )=∪ m ( n ,  m ) be the family of all connected n ‐vertex graphs. It is proved that if G ∈( n ,  m ) is such that C ( G )=max H ∈( n ,  m ) C ( H ) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C ( G )=max H ∈( n ) C ( H ) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2 n −1)/3] vertices in the clique unless n ≤9 in which case G is the n ‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000