Spanning trees on graphs and lattices inddimensions

DOI10.1088/0305-4470/33/21/303MaRDI QIDQ4489897zbMATH OpenOpenAlexFDO

Authors

Publication date 3 December 2000

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0004341

zbMATH Keywords

adjacency matrixenumerating spanning treesenumerationIsing modelLaplacian matrixlattices

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Programming involving graphs or networks (90C35)

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 $dgeq2$ dimensions, and is applied to the hypercubic, body-centered cubic, face-centered cubic, and specific planar lattices including the kagom'e, 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 $calL$ with the property that $N_{ST}simexp(n{z}_{calL})$ as the number of vertices $noinfty$, where $z_{calL}$ 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_{calL}$ exactly for the lattices we considered, and discuss the dependence of $z_{calL}$ on d and the lattice coordination number. We also establish a relation connecting $z_{calL}$ to the free energy of the critical Ising model for planar lattices $calL$.

Recommendations

• On the number of spanning trees on various lattices
• Some exact results for spanning trees on lattices
• Spanning trees on two-dimensional lattices with more than one type of vertex
• Spanning trees on lattices and integral identities
• scientific article; zbMATH DE number 1934398

Cited in

(only showing first 100 items - show all)

• Enumerating spanning trees of graphs with an involution
• On the spanning tree polyhedron
• Tutte polynomials and related asymptotic limiting functions for recursive families of graphs
• Spanning trees on hypercubic lattices and nonorientable surfaces
• Counting spanning trees in cobordism of two circulant graphs
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• New method for counting the number of spanning trees in a two-tree network
• The triangular kagomé lattices revisited
• An iteration method for computing the total number of spanning trees and its applications in graph theory
• Enumeration of spanning trees in the sequence of Dürer graphs
• On the incidence energy of some toroidal lattices
• The evaluation of the number and the entropy of spanning trees on generalized small-world networks
• The number of spanning trees of a class of self-similar fractal models
• Spanning trees in multipartite geometric graphs
• Enumeration of spanning trees in planar unclustered networks
• Potts model partition functions on two families of fractal lattices
• Asymptotic incidence energy of lattices
• The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic
• Merrifield-Simmons index and its entropy of the 4-8-8 lattice
• Complexity of the circulant foliation over a graph
• Examples of homological torsion and volume growth
• Lehmer's question, graph complexity growth and links
• Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs
• Emerging spanning trees in the work of Candilis-Josic-Woods
• A class of vertex-edge-growth small-world network models having scale-free, self-similar and hierarchical characters
• Enumeration of spanning trees of 2-separable networks
• Study of exponential growth constants of directed heteropolygonal Archimedean lattices
• Analyzing lattice networks through substructures
• Topological properties of a 3-regular small world network
• Complexity of discrete Seifert foliations over a graph
• Spanning trees and dimer problem on the Cairo pentagonal lattice
• On Jacobian group and complexity of the generalized Petersen graph \(\mathrm{GP}(n,k)\) through Chebyshev polynomials
• Enumeration of spanning trees of graphs with rotational symmetry
• The number of spanning trees in Apollonian networks
• Renormalization flow for unrooted forests on a triangular lattice
• Rooted spiral trees on hyper-cubic lattices
• The number of spanning trees of plane graphs with reflective symmetry
• On the entropy of spanning trees on a large triangular lattice
• A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks
• Vertex-colored graphs, bicycle spaces and Mahler measure
• Counting spanning trees in self-similar networks by evaluating determinants
• Families of metrized graphs with small tau constants
• Geometrically and diagrammatically maximal knots
• Asymptotic Laplacian-energy-like invariant of lattices
• On the Kirchhoff index of some toroidal lattices
• On the number of spanning trees on various lattices
• The spectrum and Laplacian spectrum of the dice lattice
• Some physical and chemical indices of clique-inserted lattices
• Enumeration of spanning trees on Apollonian networks
• Some physical and chemical indices of the Union Jack lattice
• Spanning Trees and Domination in Hypercubes
• DIMERS ON TWO-DIMENSIONAL LATTICES
• Zeta functions, heat kernels, and spectral asymptotics on degenerating families of discrete tori
• The critical group of a clique-inserted graph
• On the number of trees in Z^d
• On some Tutte polynomial sequences in the square lattice
• The asymptotic behavior of some indices of iterated line graphs of regular graphs
• High-precision entropy values for spanning trees in lattices
• Analytic properties for the honeycomb lattice Green function at the origin
• Sandpile probabilities on triangular and hexagonal lattices
• On Jacobian group and complexity of I-graph I(n, k, l) through Chebyshev polynomials
• Isomorphism of dimer configurations and spanning trees on finite square lattices
• scientific article; zbMATH DE number 1408421 (Why is no real title available?)
• The number of rooted forests in circulant graphs
• Weighted graphs, spanning tree generating functions and anisotropic lattice systems: illustrative results for the Ising and dimer models
• Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics
• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• Counting spanning trees in prism and anti-prism graphs
• On the vertex-face graphs of triangulations
• Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices
• DIMERS AND SPANNING TREES: SOME RECENT RESULTS
• Coherence in a family of tree networks with an application of Laplacian spectrum
• Some exact results for spanning trees on lattices
• Spanning trees on lattices and integral identities
• Spanning trees on two-dimensional lattices with more than one type of vertex
• The complexity of specific commuting graphs
• Spanning tree generating functions for infinite periodic graphs L and connections with simple closed random walks on L
• Graph-Theoretic Concepts in Computer Science
• Structural properties of Potts model partition functions and chromatic polynomials for lattice strips
• Exact Potts model partition functions on strips of the honeycomb lattice
• Exact Potts model partition functions on wider arbitrary-length strips of the square lattice
• On the Jacobian group of a cone over a circulant graph
• The energy and spanning trees of the Aztec diamonds
• Counting spanning trees of (1, N)-periodic graphs
• Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
• Spanning tree bounds for grid graphs
• Resistance scaling and the number of spanning trees in self-similar lattices
• The number of spanning trees in self-similar graphs
• Enumeration of spanning trees with a perfect matching of hexagonal lattices on the cylinder and Möbius strip
• The number of spanning trees for Sierpiński graphs and data center networks
• The number of spanning trees in K_n-complement of a bipartite graph
• Torsion-weighted spanning acycle entropy in cubical lattices and Mahler measures
• A unified approach to the asymptotic topological indices of various lattices
• Counting spanning trees with one perfect matching in helicene polygonal chains on the plane and cylinder
• The \(A_{\alpha}\)-spectrum and \(A_{\alpha}\)-energy of the dice lattice
• The number of spanning trees of the bipartite complement of a semiregular bipartite graph
• On the complexity of Cayley graphs on a dihedral group
• A variant of the Teufl-Wagner formula and applications
• On Jacobian group and complexity of the -graph
• The number of spanning trees in \(K_{m , n}\)-complements of bipartite graphs

This page was built for publication: Spanning trees on graphs and lattices inddimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4489897)