A note on cycle embedding in hypercubes with faulty vertices

Let fvfv denote the number of faulty vertices in an n  -dimensional hypercube. This note shows that a fault-free cycle of length of at least n2−2fv2n−2fv can be embedded in an n  -dimensional hypercube with fv=2n−3fv=2n−3 and n⩾5n⩾5. This result not only enhances the previously best known result, and also answers a question in [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821–832].

► We give the longest cycle in a hypercube with 2n−32n−3 faulty vertices. ► Our result enhances the previously known result. ► Our result answers an open question proposed by J.-S. Fu.