Spanning trees on graphs and lattices in d dimensions

The problem of enumerating spanning trees on graphs and lattices is considered. We obtain bounds on the number of spanning trees N_ST and establish inequalities relating the numbers of spanning trees of different graphs or lattices. A general formulation is presented for the enumeration of spanning trees on lattices in d ≥ 2 dimensions, and is applied to the hypercubic, body-centred cubic, face-centred cubic and specific planar lattices including the kagomé, diced, 4-8-8 (bathroom-tile), Union Jack and 3-12-12 lattices. This leads to closed-form expressions for N_ST for these lattices of finite sizes. We prove a theorem concerning the classes of graphs and lattices script L sign with the property that N_ST ∼ exp(nz_{script L sign}) as the number of vertices n → ∞, where z_{script L sign} is a finite non-zero constant. This includes the bulk limit of lattices in any spatial dimension, and also sections of lattices whose lengths in some dimensions go to infinity while others are finite. We evaluate z_{script L sign} exactly for the lattices we consider, and discuss the dependence of z_{script L sign} on d and the lattice coordination number. We also establish a relation connecting z_{script L sign} to the free energy of the critical Ising model for planar lattices.