<p>When first learning about random walks on a graph <span class="math-container">$G$</span>, one may have an intuitive feeling that adding edges to <span class="math-container">$G$</span> will decrease its cover time <span class="math-container">$C(G)$</span>.  However, this is not the case.  The <a href="https://en.wikipedia.org/wiki/Path_graph" rel="noreferrer">path graph</a> <span class="math-container">$P_n$</span> has cover time <span class="math-container">$C(P_n) = \Theta(n^2)$</span> while the <a href="http://mathworld.wolfram.com/LollipopGraph.html" rel="noreferrer">(<span class="math-container">$\frac{n}{2}$</span>, <span class="math-container">$\frac{n}{2}$</span>)-lollipop graph</a> <span class="math-container">$L_{\frac{n}{2}, \frac{n}{2}}$</span> has cover time <span class="math-container">$C(L_{\frac{n}{2}, \frac{n}{2}}) = \Theta(n^3)$</span>.  Eventually adding edges does decrease the cover time because the complete graph <span class="math-container">$K_n$</span> has cover time <span class="math-container">$C(K_n) = \Theta(n \log n)$</span> by analogy to the <a href="https://en.wikipedia.org/wiki/Coupon_collector%27s_problem" rel="noreferrer">coupon collector problem</a>.</p>
<p>Under what assumptions though would the supposed intuition hold true?  Specifically, what about <a href="https://en.wikipedia.org/wiki/Vertex-transitive_graph" rel="noreferrer">vertex transitivity</a>?</p>
<blockquote>
<p>Let <span class="math-container">$G$</span> be a vertex-transitive graph with <span class="math-container">$n$</span> vertices.  Consider any vertex-transitive graph <span class="math-container">$G^+$</span> obtained from <span class="math-container">$G$</span> by adding edges (i.e. both <span class="math-container">$G$</span> and <span class="math-container">$G^+$</span> are vertex transitive and <span class="math-container">$G$</span> is a spanning subgraph of <span class="math-container">$G^+$</span>).</p>
<p>Is it the case that <span class="math-container">$C(G^+) \le C(G)$</span>?</p>
</blockquote>

CC BY-SA 3.0
2015-11-29T07:47:46.843Z
Wouldn't the complete graph $K_{n}$ and any of its subgraphs $K_{k}$, $k < n$ be a counterexample for general vertex transitivity?
chazisop
CC BY-SA 3.0
2015-11-29T10:53:57.657Z
@chazisop Those subgraphs are not spanning.
Tyson Williams
CC BY-SA 3.0
2015-11-29T18:15:37.697Z
My bad, I confused spanning with induced.
chazisop
<graph-theory><pr.probability>
When does adding edges decrease the cover time of a graph?
Tyson Williams
# When does adding edges decrease the cover time of a graph?

(Asked by: username_0 on 2015-11-13)

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](https://en.wikipedia.org/wiki/Path_graph) $P\_n$ has cover time $C(P\_n) = \Theta(n^2)$ while the [($\frac{n}{2}$, $\frac{n}{2}$)-lollipop graph](http://mathworld.wolfram.com/LollipopGraph.html) $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](https://en.wikipedia.org/wiki/Coupon_collector%27s_problem).

Under what assumptions though would the supposed intuition hold true? Specifically, what about [vertex transitivity](https://en.wikipedia.org/wiki/Vertex-transitive_graph)?

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

**Tags:** graph-theory, pr.probability

> **Comments:**
> **username_1**: Wouldn't the complete graph $K_{n}$ and any of its subgraphs $K_{k}$, $k < n$ be a counterexample for general vertex transitivity?  
> **username_0**: @username_1 Those subgraphs are not spanning.  
> **username_1**: My bad, I confused spanning with induced.  

---

## 0 answers

