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

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)

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

(95)

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

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)