Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n  -cube, denoted by Qnk, 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⩾2n⩾2. We show that when |F|⩽2n-2|F|⩽2n-2, there exists a cycle of any length from 3 to |V(Qn3-F)| in Qn3-F. We also prove that when |F|⩽2n-3|F|⩽2n-3, there exists a path of any length from 2n-12n-1 to |V(Qn3-F)|-1 between two arbitrary nodes in Qn3-F. Since the k-ary n  -cube is regular of degree 2n2n, the fault-tolerant degrees 2n-22n-2 and 2n-32n-3 are optimal.