Long paths and cycles in faulty hypercubes: existence, optimality, complexity

A fault-free cycle in the n-dimensional hypercube Qn with f faulty vertices is long if it has length at least n2−2f. If all faulty vertices are from the same bipartite class of Qn, such length is the best possible. We prove a conjecture of Castañeda and Gotchev [N. Castañeda and I. S. Gotchev. Embedded paths and cycles in faulty hypercubes. J. Comb. Optim., 2009. doi:10.1007/s10878-008-9205-6.] asserting that where fn for every set of at most fn faulty vertices, there exists a long fault-free cycle in Qn. Furthermore, we present several results on similar problems of long paths and long routings in faulty hypercubes and their complexity.