Cover time of weighted graphs Consider a connected graph $G$ with non-negative weights on each edge. The sum of edge weights is the same for each vertex, call this sum $W$. A random walk on the graph at vertex $u$ transitions an edge $(u,v)$ with probability w(u)/W. 
The uniform weights imply a uniform staionary distribution. Can we say, that like unweighted regular graphs, the cover time is $O(n^2)$? If it helps, we can include that the maximum hitting time is known to be $O(n^2)$.
 A: You'll need some further assumption beyond just the bound on the maximum expected hitting time.
for example, for $n$ even consider a graph on $n$ vertices arranged into $n/2$ pairs. If $u$ and $v$ are a pair of vertices, let the edge between them have weight $1$, otherwise let it have weight $n^{-2}$. 
now the probability of jumping from one vertex to the other in the same pair is roughly $1-1/n$. Otherwise, the walk chooses between all other vertices uniformly at random.
so the process stays at some pair for time roughly exponential with mean $n$, before jumping to a new randomly chosen pair.  
this is essentially coupon collector. the maximum expected hitting time has order $n^2$ but the cover time has order $n^2 \log n$. 
A: A search for "algebraic connectivity" of a graph may be helpful, as well as the extensive literature on rapid mixing.
The problems mainly occur when the graph is nearly disconnected because different component-like sets have too few edges between them, or edges with weights too close to zero (which is the weight of a non-edge).  If you make certain edges exponentially small, the cover time also becomes exponential.
Your adjacency matrix has Perron root and spectral radius $W$, and the usual bounds on mixing or covering time are in terms of the eigenvalue of second-highest magnitude, as a fraction of $W$.  (Bipartite graphs are a special case, where $-W$ is also an eigenvalue.)  The limiting distribution, in this case uniform, is the $W$ eigenvector, and is the only all-positive eigenvector.  Convergence to uniform is exponential, but with base the ratio
of $W$ to other eigenvalues, by the spectral decomposition theorem.  Sometimes you can actually get a clue to the worst component-like pieces from the positive and negative parts of large eigenvectors.
