Article
Full entry |
PDF
(1.0 MB)
Feedback
PDF
(1.0 MB)
Feedback
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.
References:
[bamu-94] H.-J. Bandelt, H.M. Mulder, E. Wilkeit: Quasi-median graphs and algebras. J. Graph Theory 18 (1994), 681–703. DOI 10.1002/jgt.3190180705 | MR 1297190
[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 10.1007/BF01934458 | MR 0704996 | Zbl 0523.68057
[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 10.1016/0012-365X(92)90280-S | MR 1192372
[hinz-89] A.M. Hinz: The Tower of Hanoi. Enseign. Math. 35 (1989), 289–321. MR 1039949 | Zbl 0746.05035
[hinz-92a] A.M. Hinz: Shortest paths between regular states of the Tower of Hanoi. Inform. Sci. 63 (1992), 173–181. DOI 10.1016/0020-0255(92)90067-I | MR 1163725 | Zbl 0792.68125
[hinz-92b] A.M. Hinz: Pascal’s triangle and the Tower of Hanoi. Amer. Math. Monthly 99 (1992), 538–544. DOI 10.2307/2324061 | MR 1166003 | Zbl 0782.05003
[hisc-90] A.M. Hinz, A. Schief: The average distance on the Sierpiński gasket. Probab. Theory Related Fields 87 (1990), 129–138. DOI 10.1007/BF01217750 | MR 1076960
[imiz-75] W. Imrich, H. Izbicki: Associative products of graphs. Monatsh. Math. 80 (1975), 277–281. DOI 10.1007/BF01472575 | MR 0404058
[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 0358738 | Zbl 0288.54032
[lips-75] S. L. Lipscomb: On imbedding finite-dimensional metric spaces. Trans. Amer. Math. Soc. 211 (1975), 143–160. DOI 10.1090/S0002-9947-1975-0380751-8 | MR 0380751 | Zbl 0314.54015
[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
[milu-92] U. Milutinović: Completeness of the Lipscomb space. Glas. Mat. Ser. III 27(47) (1992), 343–364. MR 1244650
[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 10.1016/0095-8956(90)90073-9 | MR 1081222 | Zbl 0657.05023
Search
Partner of
