6
$\begingroup$

I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$).

  • However, is there a quick way to create some graph $G$ (not necessarily minimal) that has $k$ spanning trees ?

We can compute the number of spanning trees of a graph $G$ using the pseudo-determinant of the Laplacian matrix of $G$ and the number of labelled vertices (Kirchoff's theorem).

Perhaps answering the following question helps in answering the original question:

  • is there a way to generate a Laplacian matrix given its pseudo-determinant value?

Thanks in advance!

$\endgroup$

2 Answers 2

13
$\begingroup$

A $k$-cycle works if $k>2$. For $k=1$ any tree works. I don't think $k=2$ is possible unless you allow double edges: if the graph is not a tree then it has an $m$-cycle $C$ for some $m>2$; remove edges off $C$ until the graph is connected but has no cycle other than $C$, and then removing an arbitrary edge of $C$ yields at least $m$ spanning trees.

$\endgroup$
7
$\begingroup$

If $G_1$ and $G_2$ are graphs let $G_1 \vee G_2$ denote their wedge sum. That is, $G_1 \vee G_2$ is obtained by taking the one-point union of $G_1$ and $G_2$. It will not matter what vertices we decide to identify. If $G_1$ and $G_2$ have $k_1$ and $k_2$ spanning trees respectively, then $G_1 \vee G_2$ has $k_1k_2$ spanning trees.

As Noam points out a $k$-cycle has $k$ spanning trees for $k \geq 3$. So, we have a graph with $k$ spanning trees on $k$ vertices. When $k$ is composite (with some caveats for the prime $2$) we can quickly do better using the above construction. For example, if we want $k = 9$ we take $K_3 \vee K_3$ which has $5$ vertices instead of $9$.

$\endgroup$
2
  • 2
    $\begingroup$ $k \geq 3$, actually. Also, the proposer explicitly said they don't care about making the graph small, but it's still nice to know this $G_1 \vee G_2$ construction. Note, though, that it doesn't work if one of the factors must be $2$, i.e. for $k$ twice a prime or $k=8$. $\endgroup$ Jun 19, 2016 at 0:15
  • 1
    $\begingroup$ @Noam Thanks. Corrections made. Of course it should be $k \geq 3$ (especially since $k=3$ was used in my example). I figured the OP (and possibly others) might be interested in smaller graphs because of the linked question. $\endgroup$ Jun 19, 2016 at 0:27

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.