Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links
The k-ary n -cube, denoted by Q n k , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F  be a set of faulty nodes and/or edges, and n?2 n ? 2 . We show that when |F|?2n-2 | F | ? 2 n - 2 , there exists a cycle of any length from 3 to | V ( Q n 3 - F ) | in Q n 3 - F . We also prove that when |F|?2n-3 | F | ? 2 n - 3 , there exists a path of any length from 2n-1 2 n - 1 to | V ( Q n 3 - F ) | - 1 between two arbitrary nodes in Q n 3 - F . Since the k-ary n -cube is regular of degree 2n 2 n , the fault-tolerant degrees 2n-2 2 n - 2 and 2n-3 2 n - 3 are optimal.
embedding path cycle interconnection networks fault-tolerance k-ary n-cube