The number and degree distribution of spanning trees in the Tower of Hanoi graph

DOI10.1016/J.TCS.2015.10.032zbMATH Open1332.05036DBLPjournals/tcs/ZhangWLC16OpenAlexW2218183028WikidataQ57772681 ScholiaQ57772681MaRDI QIDQ897918FDOQ897918

Authors Shunqi Wu, Mingyun Li, Zhongzhi Zhang, Francesc Comellas

Publication date 8 December 2015

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

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

zbMATH Keywords

spanning treesfractal geometrydegree distributionTower of Hanoi graph

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Abstract: The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the num- ber and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.

Recommendations

• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• Enumeration of spanning trees on Apollonian networks
• The number of spanning trees in Apollonian networks
• The evaluation of the number and the entropy of spanning trees on generalized small-world networks
• Node degree distribution in spanning trees

Cites work

• Asymptotic Enumeration of Spanning Trees
• Asymptotic fringe distributions for general families of random trees
• Chromatic number and the 2-rank of a graph
• Counting spanning trees in self-similar networks by evaluating determinants
• Counting spanning trees using modular decomposition
• Enumeration problems for classes of self-similar graphs
• Farey graphs as models for complex networks
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Matrix tree theorems
• On the characterization of graphs with maximum number of spanning trees
• On unreliability polynomials and graph connectivity in reliable network synthesis
• Pfaffian orientations and perfect matchings of scale-free networks
• Resistance scaling and the number of spanning trees in self-similar lattices
• Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes
• Spanning trees of finite Sierpiński graphs
• Spanning trees on graphs and lattices inddimensions
• Spanning trees on the Sierpinski gasket
• Spanning trees: A survey
• Structure of spanning trees on the two-dimensional Sierpiński gasket
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The Tower of Hanoi -- myths and maths. With a foreword by Ian Stewart
• The number of spanning trees in Apollonian networks
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• The number of spanning trees in self-similar graphs
• Uniform spanning trees on Sierpiński graphs

Cited in

(12)

• Eigenvalues of transition weight matrix for a family of weighted networks
• Dimer coverings on the Tower of Hanoi graph
• Study of dimer-monomer on the generalized Hanoi graph
• A general method for computing Tutte polynomials of self-similar graphs
• The ice model on the three-dimensional Hanoi graph
• A tour of general Hanoi graphs
• The number of spanning trees for Sierpiński graphs and data center networks
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• A survey and classification of Sierpiński-type graphs
• Maximum matchings in scale-free networks with identical degree distribution
• The evaluation of the number and the entropy of spanning trees on generalized small-world networks
• Some two-vertex resistances of the three-towers Hanoi graph formed by a fractal graph

This page was built for publication: The number and degree distribution of spanning trees in the Tower of Hanoi graph

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