Research On The Nature Of Hanoi Tower

The Tower of Hanoi problem is a well-known puzzle. As a class of typically fractal networks, the tower of Hanoi graphs, which can be translated directly from the famous puzzle, have drawn much attention. Up to now, concerted efforts have been devoted to investigating the structural and dynamical features such as the the shortest path, average distance, planarity properties, diffusion properties, Hamilton roads, to name just a few. However, less studies such as the spanning trees, random walks and network consensus have been reported on the Tower of Hanoi graphs in spite of their great importance both theoretically and practically. In this paper, we focus on three topics:the number of spanning trees, random walks and network consensus on the Tower of Hanoi graphs.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, communi-cation aspects, synchronization, and so on. However, the practical calculation of this invariant remains a challenge, particularly for large networks. In this paper, we find an exact analytical expression for the number of spanning trees of the Tower of Hanoi graphs in both two and three dimension by numerating.Random walks on fractal media play an important role in a wide range of research fields. In this paper, we study unbiased random walks on the Tower of Hanoi graphs in d dimensions. The self-similarity and symmetry allow an analyti-cal treatment on relevant quantities for random walks on them. We first calculate the mean first-passage time (MFPT) between two particular nodes having the largest distance. After that, we determine the global mean first-passage time (GMFPT), i.e., the average of MFPTs over all pairs of nodes. We obtain exact expressions for the two quantities and their dependence relations on the network size (number of nodes). Then we determine the eigenvalue of the transition matrix of Hanoi graphs and then based on the eigenvalues we calculate the exact number of spanning trees and eigenvalue identity for random walks.Distributed consensus algorithms are important tools in the domains of multi-agent systems and the vehicle platooning problem. In addition to verifying the correctness of distributed consensus algorithms, it is also important to consider how robust these algorithms are to external disturbances. Finally we study con-sensus problems on Hanoi graphs and then draw some comparison with a class of small-world network, which share the same number of nodes and edges. We mainly focus on three important quantities of consensus problems, that is, con-vergence speed, delay robustness, and coherence for first-order (and second-order) dynamics.