The Sierpiński gasket graph of order 
, where 
is a positive integer,
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 3-sun graph (Brandstädt et al. 1999, 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 that there are exactly 
proper colorings of
using three fixed colors for every 
, as illustrated above for 
and 
. At each refinement, a proper 3-coloring
of the old graph uniquely determines the colors of the
new vertices.
Sierpiński gasket graphs are implemented in the Wolfram Language as GraphData[
"SierpinskiGasket",
n
].
