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

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 ch...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-01, Vol.609, p.443-455
Main Authors: Zhang, Zhongzhi, Wu, Shunqi, Li, Mingyun, Comellas, Francesc
Format: Article
Language:English
Subjects:
Degree distribution
Entropy
Exact solutions
Fractal geometry
Graph theory
Graphs
Invariants
Mathematical analysis
Spanning trees
Synchronization
Tower of Hanoi graph
Towers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 number 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.10.032