The Sierpiński gasket graph of order is the graph obtained from the connectivity of the Sierpiński sieve. The first few Sierpiński gasket graphs are illustrated above.
is also known as the Hajós graph or the 2-sun graph (Brandstädt et al. 1987, p. 18).
Its analog in three dimensions may be termed the Sierpiński tetrahedron graph, and it can be further generalized to higher dimensions (D. Knuth, pers. comm., May 1, 2022).
Teguia and Godbole (2006) investigated the properties of the Sierpiński gasket graphs and proved that they are Hamiltonian and pancyclic.
The graph has vertices (OEIS A067771) and edges (OEIS A000244; Teguia and Godbole 2006). It has graph diameter and domination number 1 for , 2 for , and for (Teguia and Godbole 2006).
The Sierpiński gasket graphs are uniquely 3-colorable up to permutation of colors (D. Knuth, pers. comm., Apr. 11, 2022), meaning the number of distinct colorings of is for all , as illustrated above for and . Interestingly, unique coloring follows directly from the symmetry of these graphs without needing to explicitly swap colors. The generalizations of these graphs to higher odd dimensions are also uniquely colorable (D. Knuth, pers. comm., May 1, 2022).
Sierpiński gasket graphs are implemented in the Wolfram Language as GraphData["SierpinskiGasket", n].