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

The Hamming dimension of a graph GG is introduced as the largest dimension of a Hamming graph into which GG embeds as an irredundant induced subgraph. An upper bound is proved for the Hamming dimension of Sierpiński graphs Skn, k≥3k≥3. The Hamming dimension of S3n grows as 3n−33n−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.