1-perfect codes in Sierpiński graphs

Abstract

Sierpiński graphs S ( n , κ) generalise the Tower of Hanoi graphs—the graph S ( n , 3) is isomorphic to the graph H n of the Tower of Hanoi with n disks. A 1-perfect code (or an efficient dominating set) in a graph G is a vertex subset of G with the property that the closed neighbourhoods of its elements form a partition of V ( G ). It is proved that the graphs S ( n , κ) possess unique 1-perfect codes, thus extending a previously known result for H n . An efficient decoding algorithm is also presented. The present approach, in particular the proposed (de)coding, is intrinsically different from the approach to H n .