# 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? Nov 29 '15 at 7:47
• @chazisop Those subgraphs are not spanning. Nov 29 '15 at 10:53
• My bad, I confused spanning with induced. Nov 29 '15 at 18:15