# Divisibility Relation for Spanning Trees of a Graph

Let $A = \big[{1\ 1\atop 1\ 0}\big]$, and let $G_n$ be the graph whose adjacency matrix is $A^{\otimes n}$. Also let $\kappa(G)$ denote the number of spanning trees of $G$. From a significant amount of computational evidence, it seems highly likely that that $\kappa(G_n) \mid \kappa(G_{n+1})$ always holds $n \geq 0$. In fact it seems that $\kappa(G_n)^2 \mid \kappa(G_{n+1})$. I have tried attacking this problem by analyzing the Laplacian of the graph, but this seems difficult because the Laplacian does not behave nicely under tensor product. I have been working on this for a while so I would appreciate any suggestions on how one might tackle this.

-
In the $n=1$ case -- what does it mean that one of your diagonal entries is $1$, one $0$? Does one have a self-loop the other doesn't? – Allen Knutson Apr 5 '13 at 3:30
Yes, I give one of the vertices a self-loop, so that the matrix for $G_n$ can be written nicely. It has no bearing on spanning trees of course. (Also the graph in question is formed by taking all subsets of an n-element set as vertices, and connecting disjoint subsets with edges. The loop corresponds to the empty set being disjoint from itself.) – user32835 Apr 5 '13 at 3:57
I think you should try the Q-spectrum. See Thm 2.3 (4), Thm 2.18 and bottom of page 75, Lem 2.20 of "Counting Spanning Trees", citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9128 – Martin Rubey Apr 5 '13 at 7:04

The answer is actually as nice as could be. The number of spanning trees of $G_n$ is
$$\frac{1}{3^n}2^{n 2^{n-1}}\prod_{k=0}^{n-1} \big(1-(-2)^{k-n}\big)^{\binom{n}{k}}$$