Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Michael Lugo Jul 10 '12 at 16:51
    
What is the motivation for the question? –  Felix Goldberg Jul 10 '12 at 17:02
    
you might want to look at various versions of Weighted Matrix Tree Thm, see e.g. math.uwaterloo.ca/~dgwagner/Networks.pdf –  Dima Pasechnik Jul 11 '12 at 7:36

2 Answers 2

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$.

share|improve this answer

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')}.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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