8
$\begingroup$

Hi,

Define $C(G)$ the number of spanning trees in a graph $G$.

Now, given a graph $G$ with $n$ vertices and $p$ edges, construct a new graph $G'$ which is equal to the graph $G$ but where you add exactly one new edge.

The question is : can we know something about the fraction $\frac{C(G)}{C(G')}$ ?

Perhaps we can use that the number of spanning trees of a graph is equal to the determinant of any cofactor of the laplacian matrix of the graph. (Because the two laplacian matrix are here very close) ? I tried in that way but without success yet.

$\endgroup$
3
  • 2
    $\begingroup$ Since all spanning trees of $G$ are spanning trees of $G^\prime$, you're asking what fraction of spanning trees of $G^\prime$ don't use the added edge. I doubt this will make proving anything easier but it might help the intuition. $\endgroup$ Jul 10, 2012 at 16:51
  • $\begingroup$ What is the motivation for the question? $\endgroup$ Jul 10, 2012 at 17:02
  • $\begingroup$ you might want to look at various versions of Weighted Matrix Tree Thm, see e.g. math.uwaterloo.ca/~dgwagner/Networks.pdf $\endgroup$ Jul 11, 2012 at 7:36

2 Answers 2

8
$\begingroup$

If the new edge connects vertices $v$ and $w$, then $C(G')/C(G) - 1$ is the electrical resistance between $v$ and $w$ in $G$ where all edges have a resistance of $1$. (Weighted versions work, too.) An upper bound for this resistance (providing a lower bound on $C(G)/C(G')$) is the distance between $v$ and $w$, and the maximum finite resistance occurs when $G$ is a path of $n$ vertices from $v$ to $w$, so that $C(G')$ is $n$ (spanning trees of a cycle) while $C(G) = 1$.

I would guess that the minimum resistance with $p=n+k$ edges occurs when the edge between $v$ and $w$ is as redundant as possible, with $k+2$ edges between them, with any forrest hanging off this repeated edge. That gives a resistance of $1/(k+2)$, and then $C(G) = k+2$ while $G(G') = k+3$. I think the minimum resistance is only slightly more complicated if you require the graphs to be simple: Maximize the paths of length $2$.

$\endgroup$
0
$\begingroup$

Sometimes, when dealing with concrete graphs, this bound can be handy.

Let $f(G) = max_{u \not \sim v} C(G/uv)$ where $G/uv$ is obtained after contracting two non adjacent vertices $u,v$ of $G$ into a single vertex.

From the deletion contraction recurrence we know that $$C(G') = C(G+e) = C(G)+C( (G+e)/e) \leq C(G)+f(G)$$ from where you can easily get a bound for $\frac{C(G)}{C(G')}$

In the same manner you can obtain a lower bound for $\frac{C(G)}{C(G')}.$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.