\input zb-basic
\input zb-ioport
\iteman{io-port 06045727}
\itemau{Srinivasan, Murali Krishna}
\itemti{A positive combinatorial formula for the complexity of the $q$-analog of the $n$-cube.}
\itemso{Electron. J. Comb. 19, No. 2, Research Paper P34, 14 p., electronic only (2012).}
\itemab
Summary: 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$-ana$\log 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))$.
\itemrv{~}
\itemcc{}
\itemut{spanning trees; Matrix-Tree theorem}
\itemli{emis:journals/EJC/ojs/index.php/eljc/article/view/v19i2p34}
\end