An iteration method for computing the total number of spanning trees and its applications in graph theory

DOI10.1016/j.tcs.2017.10.030zbMath1383.05054OpenAlexW2767475077MaRDI QIDQ1686071

Bing Yao, Fei Ma

Publication date: 20 December 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.10.030

zbMATH Keywords

algorithmsnumber of spanning treeswheel graphladder graphBrouwer's fixed-point theoremCayley's theorem

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Eigentime identity of the weighted scale-free triangulation networks for weight-dependent walk ⋮ Generating Fibonacci-model as evolution of networks with vertex-velocity and time-memory ⋮ Spanning tree enumeration and nearly triangular graph Laplacians ⋮ A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks ⋮ Random growth networks with exponential degree distribution ⋮ Correct proof of the main result in ``The number of spanning trees of a class of self-similar fractal models by Ma and Yao ⋮ An ensemble of random graphs with identical degree distribution ⋮ Delta invariant for Eulerian digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Spanning trees on the Sierpinski gasket
• Geometry of minimum spanning trees on scale-free networks
• 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 normalized Laplacian spectrum of subdivisions of a graph
• Enumeration of spanning trees in planar unclustered networks
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• The number of spanning trees in Apollonian networks
• Counting spanning trees in self-similar networks by evaluating determinants
• On the number of spanning trees on various lattices
• Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component
• Spanning trees on graphs and lattices inddimensions
• ON THE NORMALISED LAPLACIAN SPECTRUM, DEGREE-KIRCHHOFF INDEX AND SPANNING TREES OF GRAPHS
• The average distances in random graphs with given expected degrees
• Deterministic scale-free networks

This page was built for publication: An iteration method for computing the total number of spanning trees and its applications in graph theory