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 \geq 3\) pegs and \(n \geq 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.