TY - JOUR

T1 - The paths embedding of the arrangement graphs with prescribed vertices in given position

AU - Teng, Yuan-Hsiang

AU - Tan, Jiann-Mean

AU - Tsay, Chey-Woei

AU - Hsu, Lih-Hsing

PY - 2012/9

Y1 - 2012/9

N2 - Let n and k be positive integers with n-ka parts per thousand yen2. The arrangement graph A (n,k) is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A (n,k) . Let l be any integer with . We shall prove the following existance properties of Hamiltonian path: (1) for n-ka parts per thousand yen3 or (n,k)=(3,1), 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; (2) for n-k=2 and na parts per thousand yen5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.

AB - Let n and k be positive integers with n-ka parts per thousand yen2. The arrangement graph A (n,k) is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A (n,k) . Let l be any integer with . We shall prove the following existance properties of Hamiltonian path: (1) for n-ka parts per thousand yen3 or (n,k)=(3,1), 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; (2) for n-k=2 and na parts per thousand yen5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.

KW - Arrangement graph; Panpositionable Hamiltonian; Panconnected; Interconnection network

U2 - 10.1007/s10878-011-9418-y

DO - 10.1007/s10878-011-9418-y

M3 - Article

VL - 24

SP - 627

EP - 646

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 4

ER -