Hamiltonian Cycle in Folded Hypercubes With Highly Conditional Edge Faults

Abstract

As an extension of the n-dimensional hypercube Qn, the n-dimensional folded hypercube denoted as FQn, which can be structured from Qn adding an edge to every pair of vertices with complementary addresses.FQn possesses many properties superior to those of Qn, such as diameter, fault diameter, connectivity, and so on. In this paper, let FFe denote the set of faulty edges in FQn and assume that each vertex is incident to at least three fault-free edges in FQn - FFe. Then, we show that FQn - FFe contains a fault-free Hamiltonian cycle of length 2n, where n ≥ 3 and |FFe| ≤ 3n - 7.

Keywords

• Interconnection networks
• hypercubes
• folded hypercubes
• Hamiltonian cycle