On Some Metric Properties of the Sierpinski Graphs $S(n,k)$

Abstract

Sierpiński graphs $S(n,k)$, $n,k\in \mathbb{N}$, can be interpreted as graphs of a variant of the Tower of Hanoi with $k\ge 3$ pegs and $n\ge 1$ discs. In particular, it has been proved that for $k=3$ the graphs $S(n,3)$ are isomorphic to the Hanoi graphs $H_3^n$. In this paper, we will determine the chromatic number, the diameter, the eccentricity of a vertex, the radius, and the centre of $S(n,k)$. Moreover, we will derive an important invariant and a number-theoretical characterization of $S(n,k)$. By means of these results, we will determine the complexity of Problem $1$, that is, the complexity of getting from an arbitrary vertex $v\in S(n,k)$ to the nearest and to the most distant extreme vertex. For the Hanoi graphs $H_3^n$, some of these results are new.