Advanced Search

For any $n\ge 1$ and any $k\ge 1$, a graph $S(n,k)$ is introduced. Vertices of $S(n,k)$ are $n$-tuples over $\{1,2,...,k\}$ and two $n$-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs $S(n,3)$ are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of $S(n,k)$. Together with a formula for the distance, this result is used to compute the distance between two vertices in...