Path embeddings in faulty 3-ary n-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. In this paper, we study the problem of embedding paths of various lengths into faulty 3-ary n-cubes and prove that a faulty 3-ary n-cube with f?2n-3 faulty vertices admits a path of every length from 2n-1 to 3ⁿ-f-1 connecting any two distinct healthy vertices. This result is optimal with respect to the number of vertex faults tolerated.