Coloring Sierpinski graphs and Sierpinski gasket graphs

摘要

Sierpinski graphs S(n, 3) are the graphs of the Tower of Hanoi puzzle with n disks, while Sierpinski gasket graphs S, are the graphs naturally defined by the finite number of iterations that lead to the Sierpinski gasket. An explicit labeling of the vertices of S, is introduced. It is proved that S-n is uniquely 3-colorable, that S(n, 3) is uniquely 3-edge-colorable, and that X'(S-n) = 4, thus answering a question from [15]. It is also shown that S, contains a 1-perfect code only for n = 1 or n = 3 and that every S(n, 3) contains a unique Hamiltonian cycle.