Path Embedding in a Faulty Folded Hypercube

Let F denote the faulty vertices in an n-dimensional folded hypercube FQ(n). In this paper, we show that FQ(n) contains a fault-free path with length of at least 2(n) - 2 vertical bar F vertical bar - 1 (respectively, 2(n) - 2 vertical bar F vertical bar - 2) between two arbitrary vertices x andy of odd (respectively, even) Hamming distance in FQ(n) - F if vertical bar F vertical bar <= n - 1, where n >= 3. Since FQ(n) is (n + 1)-regular and is bipartite when n is odd, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.