Spanning Trees on Graphs and Lattices in d Dimensions

Abstract

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\ge 2$ dimensions, and is applied to the hypercubic, body-centered cubic, face-centered 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 $\mathcal{L}$ with the property that $N_{ST}\sim \exp (n{z}_{\mathcal{L}})$ as the number of vertices $n\to \infty$, where $z_{\mathcal{L}}$ is a finite nonzero 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_{\mathcal{L}}$ exactly for the lattices we considered, and discuss the dependence of $z_{\mathcal{L}}$ on d and the lattice coordination number. We also establish a relation connecting $z_{\mathcal{L}}$ to the free energy of the critical Ising model for planar lattices $\mathcal{L}$.

28 pages, latex, 1 postscript figure, J. Phys. A, in press

References in corpus (1)

• Exact Potts Model Partition Functions on Ladder Graphs

Cited by in corpus (47)

• Spanning trees on the Sierpinski gasket
• Dimers on two-dimensional lattices
• Enumeration of spanning trees in a pseudofractal scale-free web
• Spanning forests and the q-state Potts model in the limit q \to 0
• Exact Potts Model Partition Functions on Wider Arbitrary-Length Strips of the Square Lattice
• Structural Properties of Potts Model Partition Functions and Chromatic Polynomials for Lattice Strips
• Counting spanning trees in a small-world Farey graph
• Counting spanning trees in self-similar networks by evaluating determinants
• Some Exact Results for Spanning Trees on Lattices
• Geometrically and diagrammatically maximal knots
• Exact Potts Model Partition Functions on Strips of the Honeycomb Lattice
• Asymptotic energy of graphs
• Abelian Sandpile Model on the Honeycomb Lattice
• Complex-Temperature Phase Diagrams for the q-State Potts Model on Self-Dual Families of Graphs and the Nature of the $q\to \infty$ Limit
• The Number of Spanning Trees of an Infinite Family of Outerplanar, Small-World and Self-Similar Graphs
• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Spanning tree generating functions and Mahler measures
• Some physical and chemical indices of clique-inserted-lattices
• Spanning Trees on Lattices and Integration Identities
• High-Precision Entropy Values for Spanning Trees in Lattices
• Renormalization flow for unrooted forests on a triangular lattice
• Real-Space Renormalization Group for Spectral Properties of Hierarchical Networks
• Counting spanning trees on fractal graphs and their asymptotic complexity
• Spanning Trees on the Two-Dimensional Lattices with More Than One Type of Vertex
• On complexity of cyclic coverings of graphs
• A note on a hypercubic Mahler measure and associated Bessel Integral
• Counting Spanning Trees on Fractal Graphs
• Asymptotic Behavior of Acyclic and Cyclic Orientations of Directed Lattice Graphs
• Sandpile probabilities on triangular and hexagonal lattices
• Study of Exponential Growth Constants of Directed Heteropolygonal Archimedean Lattices
• Affine and topological structural entropies in granular statistical mechanics: explicit calculations and equation of state
• On Jacobian group and complexity of I-graph I(n,k,l) through Chebyshev polynomials
• Entropy of self-avoiding branching polymers: mean field theory and Monte Carlo simulations
• Asymptotic Enumeration of Spanning Trees
• On Jacobian group and complexity of the generalized Petersen graph GP(n,k) through Chebyshev polynomials
• Optimal partition recovery in general graphs
• On the entropy of spanning trees on a large triangular lattice
• Patterned and Disordered Continuous Abelian Sandpile Model
• Graph Complexity and Link Colorings
• Asymptotic Laplacian-Energy-Like Invariant of Lattices
• Sharp upper and lower bounds on the number of spanning trees in Cartesian product of graphs
• The Number of Spanning Trees in Apollonian Networks
• A challenge in enumerative combinatorics: The graph of contribution
• On rationality of generating function for the number of spanning trees in circulant graphs
• Examples of homological torsion and volume growth
• Structure of spanning trees on the two-dimensional Sierpinski gasket
• Universality and exact finite-size corrections for spanning trees on cobweb and fan networks