THE CONDITIONAL NODE CONNECTIVITY OF THE k-ARY n-CUBE
Khaled Day · Journal of Interconnection Networks · 2004
This paper derives the conditional node connectivity of the k-ary n-cube interconnection network under the condition of forbidden faulty sets (i.e. assuming that each non-faulty processor has at least one non-faulty neighbor). It is shown that under this condition and for k≥4 and n≥2, the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. The conditional node connectivity in this case is therefore 4n-2. For k=3 and n≥2 the established conditional node connectivity is 4n-3. The result for the remaining smaller values of k and n are also obtained.