Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

Authors: Klav zcaron ar S.; Milutinovi cacute U.

Source: Czechoslovak Mathematical Journal, Volume 47, Number 1, March 1997 , pp. 95-104(10)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

For any n 1 and any k 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 O(n) time. It is also shown that for k 3, the graphs S(n, k) are Hamiltonian.