The Hanoi 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 (Pool 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