Ring embedding in faulty honeycomb rectangular torus

Abstract

Assume that m and n are positive even integers with n greater than or equal to 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 e is an element of E(HReT(m, n)). Moreover, any HReT(m, n) - F is hamiltonian for any F = {a, b} with a is an element of A and b is an element of B where A and B are the bipartition of HReT(m, n), if n greater than or equal to 6 or m = 2. (C) 2002 Elsevier Science B.V. All rights reserved.