Geodesic
Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem
Czechoslovak Mathematical Journal, Tome 47 (1997) no. 1, pp. 95-104.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 05A99, 05C12, 05C38, 05C45 
@article{CMJ_1997__47_1_a6,
     author = {Klav\v{z}ar, Sandi and Milutinovi\'c, Uro\v{s}},
     title = {Graphs $S(n,k)$ and a variant of the {Tower} of {Hanoi} problem},
     journal = {Czechoslovak Mathematical Journal},
     pages = {95--104},
     publisher = {mathdoc},
     volume = {47},
     number = {1},
     year = {1997},
     mrnumber = {1435608},
     zbl = {0898.05042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1997__47_1_a6/}
}
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
SP  - 95
EP  - 104
VL  - 47
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMJ_1997__47_1_a6/
LA  - en
ID  - CMJ_1997__47_1_a6
ER  - 
%0 Journal Article
%A Klavžar, Sandi
%A Milutinović, Uroš
%T Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem
%J Czechoslovak Mathematical Journal
%D 1997
%P 95-104
%V 47
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMJ_1997__47_1_a6/
%G en
%F CMJ_1997__47_1_a6
Klavžar, Sandi; Milutinović, Uroš. Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem. Czechoslovak Mathematical Journal, Tome 47 (1997) no. 1, pp. 95-104. http://geodesic.mathdoc.fr/item/CMJ_1997__47_1_a6/