Browsing by Author "Lee, Chung-Meng"

Now showing 1 - 2 of 2

Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position
(2009-11-01)
Lee, Chung-Meng
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
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). (C) 2009 Elsevier Ltd. All rights reserved.
Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position
(2008-08-16)
Lee, Chung-Meng
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Assume that n is a positive integer with n >= 2. It is proved that between any two different vertices x and y of Q(n) there exists a path PI(x, y) of length l for any l with h(x, y) <= l <= 2(n) - 1 and 2 vertical bar(l - h(x, y)). We expect such 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 for any two vertices x and z from different partite set of n-dimensional hypercube Q(n), for any vertex y is an element of V(Q(n)) - {x, z}, and for any integer I with h(x, y) <= l <= 2(n) - l - h(y, z) and 2 vertical bar(l - h(x, y)), 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. Moreover, for any two distinct vertices x and y of Q,, and for any integer I with h(x, y) <= l <= 2(n-1) and 2 vertical bar(l - h(x, y)), there exists a hamiltonian cycle S(x, y; l) such that d(S(X,y;l))(x, y) = l. (C) 2008 Elsevier B.V. All rights reserved.