mathworld.wolfram.com

Sierpiński Gasket Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Mon Jan 21 2008
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

SierpinskiGraph

The Sierpiński gasket graph of order n is the graph obtained from the connectivity of the Sierpiński sieve. The first few Sierpiński gasket graphs are illustrated above.

S_2 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 S_n has 3(3^(n-1)-1)/2 vertices (OEIS A067771) and 3^n edges (OEIS A000244; Teguia and Godbole 2006). It has graph diameter 2^(n-1) and domination number 1 for n=1, 2 for n=2, and 3^(n-2) for n>=3 (Teguia and Godbole 2006).

SierpinskiGasketGraphColorings

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 S_n is 6=3! for all n, as illustrated above for S_2 and S_3. 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}].

See also

Hajós Graph, Hanoi Graph, Sierpiński Carpet Graph, Sierpiński Sieve, Sierpiński Tetrahedron Graph, Sun Graph, Triangular Grid Graph

Explore with Wolfram|Alpha

References

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1987.Hinz, A. M. and Schief, A. "The Average Distance on the Sierpinski Gasket." Probab. Th. Rel. Fields 87, 129-138, 1990.Knuth, D. E. Fig. 113, §7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, Dec. 5, p. 41, 2024.Sloane, N. J. A. Sequences A000244/M2807 and A067771 in "The On-Line Encyclopedia of Integer Sequences."Teguia, A. M. and Godbole, A. P. "Sierpiński Gasket Graphs and Some of Their Properties." Australasian J. Combin. 35, 181-192, 2006.

Cite this as:

Weisstein, Eric W. "Sierpiński Gasket Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SierpinskiGasketGraph.html

Subject classifications