2
$\begingroup$

Let $G$ be a connected simple graph, and identify two vertices $s$ and $t$. Let $\tau(G)$ be the number of spanning trees of $G$, and let $f(G)$ be the number of spanning forests of $G$ with $2$ components such that $s$ and $t$ are in different components.

Starting from a spanning tree of $G$, one can delete any of its $n-1$ edges to form a spanning forest with $2$ components. This gives the upper bound $f(G) \leq (n-1)\, \tau(G)$, which holds with equality if $G$ is simply an $st$-path.

Are any other upper bounds known for $f(G)$ in terms of $\tau(G)$ and other graph parameters?

I suspect another bound can be derived from the answers about effective resistance here, but I'm having trouble working one out.

$\endgroup$
  • $\begingroup$ If $st \in E(G)$, then $f(G)$ is the number of spanning trees $T$ of $G$ with $st \in E(T)$. So there is the improved bound $f(G) \leq \tau(G)$. $\endgroup$ – Tony Huynh Apr 10 '16 at 0:31
  • $\begingroup$ In general $n-1$ can be replaced by $(n-1)/c$, where $c$ is the edge-connectivity. $\endgroup$ – Brendan McKay Apr 10 '16 at 1:51
  • $\begingroup$ Did you make any progress on this question? $\endgroup$ – Lorenzo Jul 3 '18 at 22:11

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.