Longest paths and cycles in faulty hypercubes
Chun‐Nan Hung, Yihua Chang, Chao-Ming Sun · International Conference on Parallel and Distributed Computing and Networks · 2006
The length of all the previous fault-tolerant ring embedding in the hypercube Qn is at most 2n - 2fv where fv is the number faulty vertices. In this paper, we construct the fault-free cycle with 2n - 2|Fv|+2 vertices in Qn - Fv where Fv is the faulty vertices set contains at least a black vertex and a white vertex with |Fv|≤ n - 1. We also construct the fault-free path with length at least 2n - 2|Fv|+1(2n - 2|Fv|) between every pair of vertices with the different (same) color of Qn - Fv where Fv contains at least one black vertex and one white vertex with |Fv| ≤ n - 2.