Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm interested in the converse of this problem. That is, given $n$, find $G$ such that $t(G)=n$.

Without some restrictions on $G$ this problem becomes almost trivial. For example, the cycle $C_n$ has $n$ spanning trees. Additionally, if we identify a vertex of graphs $G$ and $H$, the resulting graph has $t(G) \cdot t(H)$ spanning trees. Likewise if we join $G$ and $H$ with any path. So if we could factor $n$ we would just be dealing with the same question for smaller numbers. Thus I would like to restrict $G$ from being a cycle or a graph with a cut-vertex or cut-edge.

My question is then, given $n$, can we always find a graph $G$ which is not a cycle and which has no cut-vertices or cut-edges such that $t(G)=n$? If it is possible to find one, is it possible to find many, or all graphs that satisfy those properties? If it is not possible in general, are we able to determine which $n$ it is true for?

I've gone through all of the relevant graphs up to six vertices from http://www.graphclasses.org/smallgraphs.html and calculated the number of spanning trees for each. The smallest graph which satisfies all of the criteria is $K_4-e$, which has 8 spanning trees. The first ten $n>8$ for which I haven't found a respective $G$ are 9, 10, 13, 18, 22, 25, 33, 37, 42, and 46. All of these numbers are one less than a prime or one less than 2 times a prime.

Thank you.

share|improve this question
    
The question by itself is unsolved. You may find this interesting to you as well mathoverflow.net/questions/93656/… and mathoverflow.net/questions/100816/… –  Jernej Feb 24 at 17:49
    
Thanks for your response. I'll take a look at those links and see what I can learn. –  jamisans Feb 24 at 19:17

1 Answer 1

up vote 5 down vote accepted

Let $n = pq$ for two numbers $p,q \geq 3.$ Consider the graph $B_{p,q}$ obtained by taking two cycles of length $p$ and $q$ that share a common vertex. Then $t(B_{p,q}) = pq = n.$ Hence for any $n$ that has two divisors $\geq 2$ you can find a graph satisfying your equality. Note that you can generalize this to any number of divisors of $n$ as long as they are all greater than $2.$

The second thing is to consider the theta graph $\Theta_{a,b,c}$ which is the graph obtained by taking three internally disjoint paths of length $a,b$ and $c$ respectively.

It is easy to see that $t(\Theta_{a,b,c}) = ab+ac+bc$ and hence if you can express $n = ab+ac+bc$ for $a \geq 1$ and $b,c \geq 2$ you obtain the desired graph.

It is well known that there are only finitely many numbers $n$ that are not expressible as $n = ab+ac+bc.$ They are called Euler Idoneal numbers.

Hence, for any but a finite number of $n$ you can find a $2$-connected graph satisfying your equality.

More specifically given $n \geq 2$ you can find a $2$-connected graph $G$ that is not a cycle such that $t(G) = n$ if and only if $n \not \in \{3,4,5,6,7,9,10,13,18,22,X \}.$ Where $X$ is an Idoneal number whose existence is not known. See also this paper if you're interested in this problem.

share|improve this answer
    
I hadn't heard of Idoneal numbers before. Thanks for the information and reference. –  jamisans Feb 24 at 20:18

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.