Sierpiński graphs (or Sierpiński networks) are a family of graphs defined by two parameters n {\displaystyle n} and k {\displaystyle k} , denoted S ( n , k ) {\displaystyle 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 ≥ 1 {\displaystyle n\geq 1} and k ≥ 2 {\displaystyle k\geq 2} , the Sierpiński graph S ( n , k ) {\displaystyle S(n,k)} is defined as follows:
Vertices: The vertex set V ( S ( n , k ) ) {\displaystyle V(S(n,k))} consists of all n {\displaystyle n} -tuples ( i 1 , i 2 , … , i n ) {\displaystyle (i_{1},i_{2},\ldots ,i_{n})} where each i j ∈ { 1 , 2 , … , k } {\displaystyle i_{j}\in \{1,2,\ldots ,k\}} . Thus | V ( S ( n , k ) ) | = k n {\displaystyle |V(S(n,k))|=k^{n}} . Edges: Two vertices I = ( i 1 , i 2 , … , i n ) {\displaystyle I=(i_{1},i_{2},\ldots ,i_{n})} and J = ( j 1 , j 2 , … , j n ) {\displaystyle J=(j_{1},j_{2},\ldots ,j_{n})} are adjacent if and only if there exists an h ∈ { 1 , 2 , … , n } {\displaystyle h\in \{1,2,\ldots ,n\}} such that:
i t = j t {\displaystyle i_{t}=j_{t}} for all t < h {\displaystyle t<h}
i h ≠ j h {\displaystyle i_{h}\neq j_{h}}
i t = j h {\displaystyle i_{t}=j_{h}} and j t = i h {\displaystyle j_{t}=i_{h}} for all t > h {\displaystyle t>h}
Properties The number of vertices in S ( n , k ) {\displaystyle S(n,k)} is k n {\displaystyle k^{n}} . The number of edges is n k ( k − 1 ) 2 k n − 1 {\displaystyle {\frac {nk(k-1)}{2}}k^{n-1}} . The diameter of S ( n , k ) {\displaystyle S(n,k)} is 2 n − 1 {\displaystyle 2^{n}-1} , and the chromatic number is k {\displaystyle k} . For k ≥ 3 {\displaystyle k\geq 3} , S ( n , k ) {\displaystyle S(n,k)} is Hamiltonian and has a girth of 3.
… excerpt ends here. Continue reading the full article.
