# When does adding edges decrease the cover time of a graph?

When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $P_n$ has cover time $C(P_n) = \Theta(n^2)$ while the ($\frac{n}{2}$, $\frac{n}{2}$)-lollipop graph $L_{\frac{n}{2}, \frac{n}{2}}$ has cover time $C(L_{\frac{n}{2}, \frac{n}{2}}) = \Theta(n^3)$. Eventually adding edges does decrease the cover time because the complete graph $K_n$ has cover time $C(K_n) = \Theta(n \log n)$ by analogy to the coupon collector problem.

Under what assumptions though would the supposed intuition hold true? Specifically, what about vertex transitivity?

Let $G$ be a vertex-transitive graph with $n$ vertices. Consider any vertex-transitive graph $G^+$ obtained from $G$ by adding edges (i.e. both $G$ and $G^+$ are vertex transitive and $G$ is a spanning subgraph of $G^+$).

Is it the case that $C(G^+) \le C(G)$?

• Wouldn't the complete graph $K_{n}$ and any of its subgraphs $K_{k}$, $k < n$ be a counterexample for general vertex transitivity? – chazisop Nov 29 '15 at 7:47
• @chazisop Those subgraphs are not spanning. – Tyson Williams Nov 29 '15 at 10:53
• My bad, I confused spanning with induced. – chazisop Nov 29 '15 at 18:15