The Hanoi graph 
,
where 
is an integer,
is the graph corresponding to the allowed moves for 
disks 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