TOPICS
Search

Hanoi Graph


HanoiGraph

The Hanoi graph H_n corresponding to the allowed moves in the tower of Hanoi problem. The above figure shows the Hanoi graphs for small n. The Hanoi graph H_n can be constructed by taking the vertices to be the odd binomial coefficients of Pascal's triangle computed on the integers from 0 to 2^n-1 and drawing an edge whenever coefficients are adjacent diagonally or horizontally (Pool 1994).

The graph H_n has 3^n vertices (OEIS A000244) and 3(3^n-1)/2 edges (OEIS A029858). Each Hanoi graph has a unique Hamiltonian cycle. (Equivalently, each Hanoi graph has exactly two distinct directed Hamiltonian cycles.)

H_n has 3^(n-1) small triangles, each of which can contain at most one vertex in an independent vertex set. But the triangles are arranged in the plane in such a way that choosing the apex of each gives a (maximum) independent vertex set (S. Wagon, pers. comm., Nov. 18, 2011).

Hanoi graphs are perfect and also uniquely Hamiltonian.

Hanoi graphs are implemented in the Wolfram Language as GraphData[{"Hanoi", n}].


See also

Puz-Graph, Sierpiński Gasket Graph, Tower of Hanoi

Explore with Wolfram|Alpha

References

Berend, D. and Sapir, A. "The Diameter of Hanoi Graphs." Information Processing Lett. 98, 79-85, 2006.Hinz, A. M. "Pascal's Triangle and the Tower of Hanoi." Amer. Math. Monthly 99, 538-544, 1992.Hinz, A. M. and Parisse, D. "On the Planarity of Hanoi Graphs." Expos. Math. 20, 263-268, 2002.Hinz, A. M. and Schief, A. "The Average Distance on the Sierpinski Gasket." Probab. Th. Rel. Fields 87, 129-138, 1990.Hinz, A. M.; Klavžar, S.; Milutinovć, U.; Parisse, D.; and Petr, C. "Metric Properties of the Tower of Hanoi Graphs and Stern's Diatomic Sequence." Europ. J. Combin. 26, 693-708, 2005.Lu, X. M. "Towers of Hanoi Graphs." Internat. J. Comput. Math. 19, 23-38, 1986.Lu, X. M. "Towers of Hanoi with Arbitrary k>=3 Pegs." Internat. J. Comput. Math. 24, 39-54, 1988.Poole, D. G. "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)." Math. Mag. 67, 323-344, 1994.Scorer; R. S.; Grundy, P. M.; and Smith, C. A. B. "Some Binary Games." Math. Gaz. 28, 96-103, 1944.Sloane, N. J. A. Sequences A000244/M2807 and A029858 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Hanoi Graph

Cite this as:

Weisstein, Eric W. "Hanoi Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HanoiGraph.html

Subject classifications