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