A Positive Combinatorial Formula for the Complexity of the $q$-Analog of the $n$-Cube

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 Matrix-Tree 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 Matrix-Tree 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))$.