Path embedding in faulty hypercubes

摘要

There are some interesting results concerning longest paths or even cycles embedding in faulty hypercubes. This paper considers the embeddings of paths of all possible lengths between any two fault-free vertices in faulty hypercubes. Let fv (respectively, fe) denote the number of faulty vertices (respectively, edges) in an n-dimensional hypercube Qn. We prove that there exists a fault-free path of length l between any two distinct fault-free vertices u and v in Qn with fv+fe⩽n-2 for each l satisfying dQn(u,v)+2⩽l⩽2n-2fv-1 and 2|(l-dQn(u,v)). The bounds on path length l and faulty set size fv+fe for a successful embedding are tight. That is, the result does not hold if l2n-2fv-1 or fv+fe>n-2. Moreover, our result improves some known results.