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$
3
  • $\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, 2016 at 0:31
  • $\begingroup$ In general $n-1$ can be replaced by $(n-1)/c$, where $c$ is the edge-connectivity. $\endgroup$ Apr 10, 2016 at 1:51
  • $\begingroup$ Did you make any progress on this question? $\endgroup$
    – Elle Najt
    Jul 3, 2018 at 22:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.