Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position
✍ Scribed by Chung-Meng Lee; Yuan-Hsiang Teng; Jimmy J.M. Tan; Lih-Hsing Hsu
- Publisher
- Elsevier Science
- Year
- 2009
- Tongue
- English
- Weight
- 694 KB
- Volume
- 58
- Category
- Article
- ISSN
- 0898-1221
No coin nor oath required. For personal study only.
✦ Synopsis
It is proved that there exists a path P l (x, y) of length l if d AQn (x, y) ≤ l ≤ 2 n -1 between any two distinct vertices x and y of AQ n . Obviously, we expect that such a path P l (x, y) can be further extended by including the vertices not in P l (x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that there exists a hamiltonian path R(x, y, z; l) from x to z such that d R(x,y,z;l) (x, y) = l for any three distinct vertices x, y, and z of AQ n with n ≥ 2 and for any d AQn (x, y) ≤ l ≤ 2 n -1 -d AQn (y, z). Furthermore, there exists a hamiltonian cycle S(x, y; l) such that d S(x,y;l) (x, y) = l for any two distinct vertices x and y and for any d AQn (x, y) ≤ l ≤ 2 n-1 .