Longest fault-free paths in hypercubes with vertex faults

Abstract: 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 n −2f −1 (or 2 n −2f −2) between two arbitrary vertices of odd (or even) distance. Since an n-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. [Copyright &y& Elsevier]