Embedding long cycles in faulty k-ary 2-cubes

摘要

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. Given an even k ⩾ 4, let (V1, V2) be the bipartition of the k-ary 2-cube, fv1, fv2 be the numbers of faulty vertices in V1 and V2, respectively, and fe be the number of faulty edges. In this paper, we prove that there exists a cycle of length k2 − 2max{fv1, fv2} in the k-ary 2-cube with 0 ⩽ fv1 + fv2 + fe ⩽ 2. This result is optimal with respect to the number of faults tolerated.