Panconnectivity and edge-pancyclicity of k k -ary n n -cubes with faulty elements ?
The class of k k -ary n n -cubes represents the most commonly used interconnection topology for parallel and distributed computing systems. In this paper, we investigate the fault-tolerant capabilities of the k k -ary n n -cubes for odd integer k k with respect to the panconnectivity and pancyclicity. By studying first the fault panconnectivity of two-dimensional torus networks and then using an induction argument, we prove that in a k k -ary n n -cube Q n k with odd k?3 k ? 3 , every pair of healthy vertices of Q n k are connected by fault-free paths of lengths from n(k?1)?1 n ( k ? 1 ) ? 1 to | V ( Q n k ? F ) | ? 1 and every healthy edge is contained in fault-free cycles of lengths from n(k?1) n ( k ? 1 ) to | V ( Q n k ? F ) | for any set F F of faulty elements (vertices and/or edges) with |F|?2n?3 | F | ? 2 n ? 3 . Finally, examples show that our results are best possible in some sense.
panconnectivity torus interconnection network k k -ary n n -cube k k k k k n n n n n fault tolerance path embedding