Long paths and cycles in hypercubes with faulty vertices

A fault-free path in the nn-dimensional hypercube QnQn with ff faulty vertices is said to be long   if it has length at least 2n-2f-22n-2f-2. Similarly, a fault-free cycle in QnQn is long if it has length at least 2n-2f2n-2f. If all faulty vertices are from the same bipartite class of QnQn, such length is the best possible. We show that for every set of at most 2n-42n-4 faulty vertices in QnQn and every two fault-free vertices uu and vv satisfying a simple necessary condition on neighbors of uu and vv, there exists a long fault-free path between uu and vv. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n2/10+n/2+1n2/10+n/2+1 faulty vertices in QnQn where n⩾15n⩾15 that QnQn has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.