Linear array and ring embeddings in conditional faulty hypercubes

AbstractThe n-dimensional hypercube Qn is a graph having 2n vertices labeled from 0 to 2n−1. Two vertices are connected by an edge if their binary labels differ in exactly one bit position. In this paper, we consider the faulty hypercube Qn with n⩾3 that each vertex of Qn is incident to at least two nonfaulty edges. Based on this requirement, we prove that Qn contains a hamiltonian path joining any two different colored vertices even if it has up to 2n−5 edge faults. Moreover, we show that there exists a path of length 2n−2 between any two the same colored vertices in this faulty Qn. Furthermore, we also prove that the faulty Qn still contains a cycle of every even length from 4 to 2n inclusive