
Murali Krishna Srinivasan
Abstract
The number of spanning trees of a graph $G$ is called the complexity of $G$. A classical result in algebraic graph theory explicitly diagonalizes the Laplacian of the $n$cube $C(n)$ and yields, using the MatrixTree theorem, an explicit formula for $c(C(n))$. In this paper we explicitly block diagonalize the Laplacian of the $q$analog $C_q(n)$ of $C(n)$ and use this, along with the MatrixTree theorem, to give a positive combinatorial formula for $c(C_q(n))$. We also explain how setting $q=1$ in the formula for $c(C_q(n))$ recovers the formula for $c(C(n))$.