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)$?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.