Sierpiński graph

Sierpiński graphs (or Sierpiński networks) are a family of graphs defined by two parameters $n$ and $k$, denoted $S(n,k)$. 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 $n\ge 1$ and $k\ge 2$, the Sierpiński graph $S(n,k)$ is defined as follows:

• Vertices: The vertex set $V(S(n,k))$ consists of all $n$-tuples $(i_1,i_2,\dots ,i_n)$ where each $i_j\in \{1,2,\dots ,k\}$. Thus $|V(S(n,k))|=k^n$.

• Edges: Two vertices $I=(i_1,i_2,\dots ,i_n)$ and $J=(j_1,j_2,\dots ,j_n)$ are adjacent if and only if there exists an $h\in \{1,2,\dots ,n\}$ such that:
  • $i_t=j_t$ for all $t<h$
  • $i_h\ne j_h$
  • $i_t=j_h$ and $j_t=i_h$ for all $t>h$

Properties

The number of vertices in $S(n,k)$ is $k^n$. The number of edges is $\frac{nk(k-1)}{2}{k}^{n-1}$.

The diameter of $S(n,k)$ is $2^n-1$, and the chromatic number is $k$.

For $k\ge 3$, $S(n,k)$ is Hamiltonian and has a girth of 3.

Relationship to Tower of Hanoi

Sierpiński graphs $S(n,k)$ are the state graphs for a variant of the Tower of Hanoi problem. In this variant, the vertices of $S(n,k)$ represent the $k^n$ possible arrangements of $n$ disks on $k$ pegs. An edge represents a legal move, which is defined as follows: for a move between peg $i$ and peg $j$, find the largest disk $h$ that is not on pegs $i$ or $j$. All disks smaller than $h$ must be on a single peg, and the move consists of transferring them between pegs $i$ and $j$.

Notably, for $k=3$, the graph $S(n,3)$ is isomorphic to the graph of the classical Tower of Hanoi with $n$ disks.

Applications

Interconnection networks

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

• They have a low and bounded degree, simplifying expansion and meeting VLSI pin constraints.
• The hierarchical structure matches traffic patterns in many parallel applications.
• They provide scalable costs and performance for future parallel computer systems and LANs.

Efficient dominating sets

Sierpiński graphs $S(n,k)$ possess essentially unique efficient dominating sets for all parameters $n$ and $k$, 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

• $S(n,1)$: The single vertex graph $K_1$
• $S(n,2)$: The path graph $P_{2^n}$
• $S(1,k)$: The complete graph $K_k$
• $S(n,3)$: Isomorphic to the Tower of Hanoi graph with $n$ disks

See also

• Sierpiński triangle
• Tower of Hanoi
• Hanoi graph
• Interconnection network
• Topological index

External links

• Sierpiński Graph at MathWorld