The number of spanning trees in Apollonian networks

DOI10.1016/J.DAM.2014.01.015MaRDI QIDQ2449073zbMATH OpenOpenAlexWikidataFDO

Authors Bin Wu, Zhongzhi Zhang, Francesc Comellas

Publication date 6 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0090

zbMATH Keywords

Apollonian networkscomplex networksmaximally planarscale-freeself-similarsmall-world graphsspanning trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: In this paper we find an exact analytical expression for the number of spanning trees in Apollonian networks. This parameter can be related to significant topological and dynamic properties of the networks, including percolation, epidemic spreading, synchronization, and random walks. As Apollonian networks constitute an interesting family of maximal planar graphs which are simultaneously small-world, scale-free, Euclidean and space filling and highly clustered, the study of their spanning trees is of particular relevance. Our results allow also the calculation of the spanning tree entropy of Apollonian networks, which then we compare with those of other graphs with the same average degree.

Recommendations

• Enumeration of spanning trees on Apollonian networks
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• Enumeration of spanning trees in planar unclustered networks
• The evaluation of the number and the entropy of spanning trees on generalized small-world networks
• Counting spanning trees in prism and anti-prism graphs

Cites work

• Asymptotic Enumeration of Spanning Trees
• Counting spanning trees in self-similar networks by evaluating determinants
• High-dimensional Apollonian networks
• High-precision entropy values for spanning trees in lattices
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Information theory of complex networks: on evolution and architectural constraints
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Resistance scaling and the number of spanning trees in self-similar lattices
• Spanning trees of finite Sierpiński graphs
• Spanning trees on graphs and lattices inddimensions
• Spanning trees on the Sierpinski gasket
• The Apollonian Packing of Circles
• The Structure and Function of Complex Networks

Cited in

(34)

• Enumeration of spanning trees on contact graphs of disk packings
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
• 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
• Enumeration of spanning trees in planar unclustered networks
• Potts model partition functions on two families of fractal lattices
• Correct proof of the main result in ``The number of spanning trees of a class of self-similar fractal models by Ma and Yao
• The relations between network-operation and topological-property in a scale-free and small-world network with community structure
• A class of vertex-edge-growth small-world network models having scale-free, self-similar and hierarchical characters
• A family of small-world network models built by complete graph and iteration-function
• Generating Fibonacci-model as evolution of networks with vertex-velocity and time-memory
• Strong geodetic problem in networks
• Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
• Laplacian spectra for categorical product networks and its applications
• Pfaffian orientations and perfect matchings of scale-free networks
• A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks
• Tutte polynomial of scale-free networks
• On constructing rational spanning tree edge densities
• On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs
• Enumeration of spanning trees on Apollonian networks
• Tutte polynomial of the Apollonian network
• The number of spanning trees in a class of double fixed-step loop networks
• Volume bounds for the phase-locking region in the Kuramoto model with asymmetric coupling
• Counting spanning trees in prism and anti-prism graphs
• Random growth networks with exponential degree distribution
• Leader-follower coherence of the weighted recursive tree networks
• Modeling spatial networks by contact graphs of disk packings
• Spectral analysis of weighted neighborhood networks
• Computing the number and average size of connected sets in planar 3-trees
• Random growth scale-free networked models with an identical degree distribution and a tunable assortativity index
• The number of spanning trees for Sierpiński graphs and data center networks
• The coherence analysis and Laplacian spectrum applications of cycle-based iterative networks
• The number and degree distribution of spanning trees in the Tower of Hanoi graph

This page was built for publication: The number of spanning trees in Apollonian networks

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