Spanning trees on graphs and lattices inddimensions

DOI10.1088/0305-4470/33/21/303zbMATH Open0949.05041arXivcond-mat/0004341OpenAlexW2001149343MaRDI QIDQ4489897FDOQ4489897

Authors:

Publication date: 3 December 2000

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

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$.

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

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

zbMATH Keywords

latticesenumerationLaplacian matrixadjacency matrixIsing modelenumerating spanning trees

Mathematics Subject Classification ID

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

Cited In (95)

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