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.
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