TY - JOUR

T1 - Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position

AU - Lee, Chung-Meng

AU - Teng, Yuan-Hsiang

AU - Tan, Jiann-Mean

AU - Hsu, Lih Hsing

PY - 2009/11

Y1 - 2009/11

N2 - 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.

AB - 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.

KW - Hamiltonian; Augmented cubes

U2 - 10.1016/j.camwa.2009.07.079

DO - 10.1016/j.camwa.2009.07.079

M3 - Article

VL - 58

SP - 1762

EP - 1768

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 9

ER -