Spanning trees of ladder graphs...

Question

a. Draw the 1-ladder, 2-ladder, and 3-ladder graphs, and calculate the number of spanning trees for each. - I have completed this part and wanted to confirm that these numbers look accurate, I feel like i was able to get all of them.

b. A spanning tree of a connected graph $G$ is a a tree which contains all the vertices of $G$ and which is a subgraph of $G$. If $T(n)$ is the number of spanning trees for the $n$-ladder, then $T(n)=4 · T(n - 1) - T(n - 2)$. Solve this recurrence relation to obtain a closed formula the number of spanning trees for a $n$-ladder. I don't really know how to do this part of the problem and would appreciate any help.

Answer 1

You can verify that there are $6 + 9 = 15$ spanning trees of the $3$-ladder graph.

To see this, note that you must remove $2$ edges.

1. If the center edge is removed, we can remove any one of the remaining $6$ edges.
2. If the center edge is not removed, we remove one edge from each side - there are $3$ choices per side, so a total of $9$ possibilities.

For part b, which techniques have you seen for solving recurrence relations?

You can find the characteristic polynomial to find the general solution. In this case we get $r^2 - 4r + 1 = 0$, so $r = \frac{4 \pm \sqrt{12}}{2} = 2 \pm \sqrt{3}$. Then, $T(n) = c_1 (2 + \sqrt{3})^n + c_2(2 - \sqrt{3})^n$. Solve for the constants using the initial values $T(1) = 1$ and $T(2) = 4$.

Answer 2

Another interesting "ladder" graph is the so-called Mobius ladder $M_n$ of order $n$. Namely, take cycle graph with $2n$ vertices and then add $n$ edges that connect every vertex with its diametrically opposite counterpart. Another way to describe it is to take a regular ladder graph with $n+1$ levels and then glue the two vertices of level $1$ with two vertices of level $n+1$, flipping the sides (left vertex of level $1$ will become the same as the right vertex of level $n+1$, and vice versa).

Then there exists a very similar formula for $t(M_n)$, that is, for the number of spanning trees of $M_n$.

Alas, I never saw any "decent" formula for $t(Sq_{\,n,m})$ where $Sq_{\,n,m}$ is the graph of two-dimensional square grid with dimensions $m\times n$ (this would be the most obvious generalization of order $n$ ladder graph). I am sure it is possible to produce a fairly manageable formula for $t(Sq_{\,3,m})$ but it probably looks rather ugly... although I just might be wrong.