Hamming dimension of a graph—The case of Sierpiński graphs

The Hamming dimension of a graph G is introduced as the largest dimension of a Hamming graph into which G embeds as an irredundant induced subgraph. An upper bound is proved for the Hamming dimension of Sierpiński graphs S k n , k ≥ 3 . The Hamming dimension of S 3 n grows as 3 n − 3 . Several explicit embeddings are constructed along the way, in particular into products of generalized Sierpiński triangle graphs. The canonical isometric representation of Sierpiński graphs is also explicitly described.