Sharp upper and lower bounds on the number of spanning trees in Cartesian product of graphs

Let $G_1$ and $G_2$ be simple graphs and let $n_1=\mathrm{\mid }V(G_1)\mathrm{\mid }$, $m_1 = |E(G_1)|$,$n_2 = |V(G_2)|$and$m_2 = |E(G_2)|.$ In this paper we derive sharp upper and lower bounds for the number of spanning trees $\tau$ in the Cartesian product $G_1\mathrm{\square }{G}_2$ of $G_1$ and $G_2$. We show that: $$\tau (G_1\mathrm{\square }{G}_2)\ge \frac{2^{(n_1-1)(n_2-1)}}{n_1{n}_2}(\tau (G_1)n_1{)}^{\frac{n_2+1}{2}}(\tau (G_2)n_2{)}^{\frac{n_1+1}{2}}$$ and $$\tau (G_1\mathrm{\square }{G}_2)\le \tau (G_1)\tau (G_2)[\frac{2m_1}{n_1-1}+\frac{2m_2}{n_2-1}{]}^{(n_1-1)(n_2-1)}\mathrm{.}$$ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in $K_{n_1}\mathrm{\square }{K}_{n_2}$ which turns out to be $n_1^{n_1-2}{n}_2^{n_2-2}(n_1+n_2{)}^{(n_1-1)(n_2-1)}\mathrm{.}$