2000/04/19 by R. Shrock, Robert Shrock, F. Y. Wu · 1 citation
Mathematics · Physics and Astronomy · #Combinatorics #Condensed matter physics #Cubic crystal system #Discrete mathematics #Enumeration #Graph #Lattice (music) #Limit (mathematics) #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Physics #Planar #Planar graph #Spanning tree #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.stat-mech #hep-lat #math-ph #math.MP
paper · pdf · doi:10.1088/0305-4470/33/21/303
published as J.Phys.A33:3881-3902,2000 · 28 pages, latex, 1 postscript figure, J. Phys. A, in press
arxiv created 2000/04/19 · openalex publication_date 2000/05/18 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 with the property that N ST ~exp ( nz ) as the number of vertices n → ∞ , where z 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 exactly for the lattices we consider, and discuss the dependence of z on d and the lattice coordination number. We also establish a relation connecting z to the free energy of the critical Ising model for planar lattices.