Fault-tolerant embedding of cycles of various lengths in k-ary n-cubes

摘要

The k-ary n-cube has been one of the most popular interconnection networks for distributed-memory parallel systems. In this paper, we study the problem of embedding cycles of various lengths into faulty k-ary n-cubes. It is proved that a faulty k-ary n-cube with f_v faulty vertices and f_e faulty edges admits a fault-free cycle of every even length from 4 to k~n - 2f_v if k ≥ 4 is even and f_v + f_e ≤ in 2n - 2. Furthermore, we show that every healthy edge of the faulty k-ary n-cube lies on a fault-free cycle of every even length from 4 to k~n - 2f_v if k ≥4 is even and f_v + f_e ≤2n - 3. The results are optimal with respect to the number of vertex and edge faults tolerated.