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

DOI10.1016/J.TCS.2015.10.032zbMATH Open1332.05036DBLPjournals/tcs/ZhangWLC16arXiv1510.07949OpenAlexW2218183028WikidataQ57772681 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)

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.

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

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

zbMATH Keywords

spanning treesfractal geometrydegree distributionTower of Hanoi graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)