Embedded paths and cycles in faulty hypercubes

An important task in the theory of hypercubes is to establish the maximum integer f _n such that for every set ℱ of f vertices in the hypercube Q_n,{mathcal {Q}}_{n}, with 0≤f≤f _n , there exists a cycle of length at least 2 ⁿ −2f in the complement of ℱ. Until recently, exact values of f _n were known only for n≤4, and the best lower bound available for f _n with n≥5 was 2n−4. We prove that f ₅=8 and obtain the lower bound f _n ≥3n−7 for all n≥5. Our results and an example provided in the paper support the conjecture that f_n=((n) || 2)-2f_{n}={nchoose 2}-2 for each n≥4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved.