| Title:
|
Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem (English) |
| Author:
|
Klavžar, Sandi |
| Author:
|
Milutinović, Uroš |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
47 |
| Issue:
|
1 |
| Year:
|
1997 |
| Pages:
|
95-104 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| MSC:
|
05A99 |
| MSC:
|
05C12 |
| MSC:
|
05C38 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 0898.05042 |
| idMR:
|
MR1435608 |
| . |
| Date available:
|
2009-09-24T10:02:49Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127341 |
| . |
| Reference:
|
[bamu-94] H.-J. Bandelt, H.M. Mulder, E. Wilkeit: Quasi-median graphs and algebras.J. Graph Theory 18 (1994), 681–703. MR 1297190, 10.1002/jgt.3190180705 |
| Reference:
|
[clau-84] N. Claus (= E. Lucas): La Tour d’Hanoi, Jeu de calcul.Science et Nature 1(8) (1884), 127–128. |
| Reference:
|
[er-83] M.C. Er: An analysis of the generalized Towers of Hanoi problem.BIT 23 (1983), 295–302. Zbl 0523.68057, MR 0704996, 10.1007/BF01934458 |
| Reference:
|
[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. MR 1192372, 10.1016/0012-365X(92)90280-S |
| Reference:
|
[hinz-89] A.M. Hinz: The Tower of Hanoi.Enseign. Math. 35 (1989), 289–321. Zbl 0746.05035, MR 1039949 |
| Reference:
|
[hinz-92a] A.M. Hinz: Shortest paths between regular states of the Tower of Hanoi.Inform. Sci. 63 (1992), 173–181. Zbl 0792.68125, MR 1163725, 10.1016/0020-0255(92)90067-I |
| Reference:
|
[hinz-92b] A.M. Hinz: Pascal’s triangle and the Tower of Hanoi.Amer. Math. Monthly 99 (1992), 538–544. Zbl 0782.05003, MR 1166003, 10.2307/2324061 |
| Reference:
|
[hisc-90] A.M. Hinz, A. Schief: The average distance on the Sierpiński gasket.Probab. Theory Related Fields 87 (1990), 129–138. MR 1076960, 10.1007/BF01217750 |
| Reference:
|
[imiz-75] W. Imrich, H. Izbicki: Associative products of graphs.Monatsh. Math. 80 (1975), 277–281. MR 0404058, 10.1007/BF01472575 |
| Reference:
|
[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. Zbl 0288.54032, MR 0358738 |
| Reference:
|
[lips-75] S. L. Lipscomb: On imbedding finite-dimensional metric spaces.Trans. Amer. Math. Soc. 211 (1975), 143–160. Zbl 0314.54015, MR 0380751, 10.1090/S0002-9947-1975-0380751-8 |
| Reference:
|
[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 1093602 |
| Reference:
|
[milu-92] U. Milutinović: Completeness of the Lipscomb space.Glas. Mat. Ser. III 27(47) (1992), 343–364. MR 1244650 |
| Reference:
|
[milu-94] U. Milutinović: A universal separable metric space of Lipscomb’s type.Preprint Series Univ. of Ljubljana 32 (1994), 443. |
| Reference:
|
[wilk-90] E. Wilkeit: Isometric embeddings in Hamming graphs.J. Combin. Theory Ser. B 50 (1990), . Zbl 0657.05023, MR 1081222, 10.1016/0095-8956(90)90073-9 |
| . |
