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.

Improve this question
$\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$
    – Michael Lugo
    Commented Jul 10, 2012 at 16:51
  • $\begingroup$ What is the motivation for the question? $\endgroup$
    – Felix Goldberg
    Commented 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$
    – Dima Pasechnik
    Commented Jul 11, 2012 at 7:36

2 Answers 2

Reset to default
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$.

Improve this answer
$\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')}.$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .