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.



Divisibility Relation for Spanning Trees of a Graph
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}}
$$


This follows directly from the theorems in the comment above. The divisibility (what a beautiful word!) properties then follow from the formula.


