The Hanoi graph 
is the graph corresponding to the allowed moves in the
tower of Hanoi problem. The above figure shows the
Hanoi graphs for small 
.
The Hanoi graph 
can be constructed by taking the vertices to be the
odd binomial coefficients
of Pascal's triangle computed on the integers
from 0 to 
and drawing an edge whenever coefficients
are adjacent diagonally or horizontally (Poole 1994).
The graph 
has 
vertices (OEIS A000244)
and 
edges
(OEIS A029858). Each Hanoi graph has a unique
Hamiltonian cycle. (Equivalently, each Hanoi
graph has exactly two distinct directed Hamiltonian
cycles.)
has 
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. The figure above shows the regions enclosed by the unique Hamiltonian
cycle of the 
-Hanoi
graph with 
,
..., 6.
Hanoi graphs are implemented in the Wolfram Language as GraphData[
"Hanoi", n
].
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