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

Jernej Azarija

paper

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

arXiv:1210.6340

Abstract

Let $G_{1}$ and $G_{2}$ be simple graphs and let $n_{1} = ∣ V (G_{1}) ∣$ , $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 $τ$ in the Cartesian product $G_{1} □ G_{2}$ of $G_{1}$ and $G_{2}$ . We show that: $τ (G_{1} □ G_{2}) \geq \frac{2 ^{(n_{1} - 1) (n_{2} - 1)}}{n _{1} n _{2}} (τ (G_{1}) n_{1})^{\frac{n _{2} + 1}{2}} (τ (G_{2}) n_{2})^{\frac{n _{1} + 1}{2}}$ and $τ (G_{1} □ G_{2}) \leq τ (G_{1}) τ (G_{2}) [\frac{2 m _{1}}{n _{1} - 1} + \frac{2 m _{2}}{n _{2} - 1}]^{(n_{1} - 1) (n_{2} - 1)} .$ 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}} □ 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)} .$

References in corpus (1)

Spanning Trees on Graphs and Lattices in d Dimensions