Cycle Embedding in Faulty Folded Hypercube

Abstract

n this article, we analyze the edge-fault-tolerant properties of the n-dimensional folded hypercube, which is an extension of a hypercube, obtained by adding some complementary edges. A vertex in the n-dimensional folded hypercube is k-fault-free node if it is incident with exactly k fault-free edges. We show that if there is at most one 2-fault-free node and each of the other nodes incident to at least three fault-free edges in any n-dimensional folded hypercube (n ≥ 3) with at most 2n−2 faulty edges, there exists a Hamiltonian cycle. We also show that it contains a fault-free Hamiltonian cycle if an arbitrary fault-free edge in the n-dimensional folded hypercube with 2n − 2 faulty edges such that its end-nodes are 2-fault-free nodes.