Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem

Klavžar, Sandi, and Milutinović, Uroš. "Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem." Czechoslovak Mathematical Journal 47.1 (1997): 95-104. <http://eudml.org/doc/30349>.

@article{Klavžar1997,
abstract = {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 $\lbrace 1, 2, \ldots , k\rbrace $ 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\ge 3$, the graphs $S(n,k)$ are Hamiltonian.},
author = {Klavžar, Sandi, Milutinović, Uroš},
journal = {Czechoslovak Mathematical Journal},
keywords = {Tower of Hanoi; Hamiltonian graph; distance in a graph},
language = {eng},
number = {1},
pages = {95-104},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem},
url = {http://eudml.org/doc/30349},
volume = {47},
year = {1997},
}

TY - JOUR
AU - Klavžar, Sandi
AU - Milutinović, Uroš
TI - Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem
JO - Czechoslovak Mathematical Journal
PY - 1997
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 47
IS - 1
SP - 95
EP - 104
AB - 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 $\lbrace 1, 2, \ldots , k\rbrace $ 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\ge 3$, the graphs $S(n,k)$ are Hamiltonian.
LA - eng
KW - Tower of Hanoi; Hamiltonian graph; distance in a graph
UR - http://eudml.org/doc/30349
ER -