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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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^{n1}}\prod_{k=0}^{n1} \big(1(2)^{kn}\big)^{\binom{n}{k}} $$ This follows directly from the theorems in the comment above. The divisibility (what a beautiful word!) properties then follow from the formula. 

