Sierpiński graph


Sierpiński graphs are a family of graphs defined by two parameters and, denoted. These graphs have applications in topology, Tower of Hanoi problems, and interconnection networks for multiprocessor systems. The graphs are named after Wacław Sierpiński due to their connections with Sierpiński fractals.

Definition

For any integers and, the Sierpiński graph is defined as follows:Vertices: The vertex set consists of all -tuples where each. Thus.Edges: Two vertices and are adjacent if and only if there exists an such that:
  • * for all
  • *
  • * and for all

Properties

The number of vertices in is. The number of edges is.
The diameter of is, and the chromatic number is.
For, is Hamiltonian and has a girth of 3.

Relationship to Tower of Hanoi

Sierpiński graphs are the state graphs for a variant of the Tower of Hanoi problem. In this variant, the vertices of represent the possible arrangements of disks on pegs. An edge represents a legal move, which is defined as follows: for a move between peg and peg, find the largest disk that is not on pegs or. All disks smaller than must be on a single peg, and the move consists of transferring them between pegs and.
Notably, for, the graph is isomorphic to the graph of the classical Tower of Hanoi with disks.

Applications

Interconnection networks

Sierpiński graphs have been proposed as topologies for interconnection networks in computer architecture:

Efficient dominating sets

Sierpiński graphs possess essentially unique efficient dominating sets for all parameters and, making them important examples in the study of domination in graphs. An efficient dominating set is also known as a 1-perfect code.

Special cases