Longest fault-free paths in hypercubes with vertex faults

The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This Study demonstrates that when f <= n - 2, the n-cube contains a fault-free path with length at least 2" - 2f - 1 (or 2" - 2f - 2) between two arbitrary vertices of odd (or even) distance. Since an 17-CUbe is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the Connectivity of an n-cube is n, the n-cube cannot tolerate n - 1 faulty vertices. Hence, our result is optimal. (c) 2005 Elsevier Inc. All rights reserved.