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 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {1997},
     volume = {47},
     number = {1},
     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
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
%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/

[bamu-94] H.-J. Bandelt, H.M. Mulder, E. Wilkeit: Quasi-median graphs and algebras. J. Graph Theory 18 (1994), 681–703. | DOI | MR

[clau-84] N. Claus (= E. Lucas): La Tour d’Hanoi, Jeu de calcul. Science et Nature 1(8) (1884), 127–128.

[er-83] M.C. Er: An analysis of the generalized Towers of Hanoi problem. BIT 23 (1983), 295–302. | DOI | MR | Zbl

[fesc-92] J. Feigenbaum, A.A. Schäffer: Finding the prime factors of strong direct product graphs in polynomial time. Discrete Math. 109 (1992), 77–102. | DOI | MR

[hinz-89] A.M. Hinz: The Tower of Hanoi. Enseign. Math. 35 (1989), 289–321. | MR | Zbl

[hinz-92a] A.M. Hinz: Shortest paths between regular states of the Tower of Hanoi. Inform. Sci. 63 (1992), 173–181. | DOI | MR | Zbl

[hinz-92b] A.M. Hinz: Pascal’s triangle and the Tower of Hanoi. Amer. Math. Monthly 99 (1992), 538–544. | DOI | MR | Zbl

[hisc-90] A.M. Hinz, A. Schief: The average distance on the Sierpiński gasket. Probab. Theory Related Fields 87 (1990), 129–138. | DOI | MR

[imiz-75] W. Imrich, H. Izbicki: Associative products of graphs. Monatsh. Math. 80 (1975), 277–281. | DOI | MR

[lips-74] S. L. Lipscomb: A universal one-dimensional metric space. TOPO 72—General Topology and its Applications, Second Pittsburgh Internat. Conf., Volume 378 of Lecture Notes in Math., Springer-Verlag, New York, 1974, pp. 248–257. | MR | Zbl

[lips-75] S. L. Lipscomb: On imbedding finite-dimensional metric spaces. Trans. Amer. Math. Soc. 211 (1975), 143–160. | DOI | MR | Zbl

[lipe-92] S. L. Lipscomb, J. C. Perry: Lipscomb’s $L(A)$ space fractalized in Hilbert’s $l^2(A)$ space. Proc. Amer. Math. Soc. 115 (1992), 1157–1165. | MR

[milu-92] U. Milutinović: Completeness of the Lipscomb space. Glas. Mat. Ser. III 27(47) (1992), 343–364. | MR

[milu-94] U. Milutinović: A universal separable metric space of Lipscomb’s type. Preprint Series Univ. of Ljubljana 32 (1994), 443.

[wilk-90] E. Wilkeit: Isometric embeddings in Hamming graphs. J. Combin. Theory Ser. B 50 (1990), . | DOI | MR | Zbl