Long paths and cycles in hypercubes with faulty vertices

Abstract

We show that for every set of at most 2n - 4 faulty vertices in n-dimension hypercube and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v.

Keywords

• paths
• cycles
• hypercubes
• faulty
• vertices