TY - JOUR

T1 - Ring embedding in faulty honeycomb rectangular torus

AU - Cho, Hsun-Jung

AU - Hsu, Li Yen

PY - 2002/12/16

Y1 - 2002/12/16

N2 - Assume that m and n are positive even integers with n ≥ 4. The honeycomb rectangular torus HReT(m, n) is recognized as another attractive alternative to existing torus interconnection networks in parallel and distributed applications. It is known that any HReT(m, n) is a 3-regular bipartite graph. We prove that any HReT(m, n) - e is hamiltonian for any edge eE(HReT(m, n)). Moreover, any HReT(m, n) - F is hamiltonian for any F = (a, b) with a ∈ A and b ∈ B where A and B are the bipartition of HReT(m, n), if n ≥ 6 or m = 2.

AB - Assume that m and n are positive even integers with n ≥ 4. The honeycomb rectangular torus HReT(m, n) is recognized as another attractive alternative to existing torus interconnection networks in parallel and distributed applications. It is known that any HReT(m, n) is a 3-regular bipartite graph. We prove that any HReT(m, n) - e is hamiltonian for any edge eE(HReT(m, n)). Moreover, any HReT(m, n) - F is hamiltonian for any F = (a, b) with a ∈ A and b ∈ B where A and B are the bipartition of HReT(m, n), if n ≥ 6 or m = 2.

KW - Hamiltonian cycle

KW - Honeycomb torus

KW - Interconnection networks

KW - Ring embedding

UR - http://www.scopus.com/inward/record.url?scp=0037121492&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(02)00310-1

DO - 10.1016/S0020-0190(02)00310-1

M3 - Article

AN - SCOPUS:0037121492

VL - 84

SP - 277

EP - 284

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -