Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4635069 | Applied Mathematics and Computation | 2007 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Meijie Ma, Guizhen Liu, Xiangfeng Pan,