The conditional fault-diameter of the K-ary n-cube

الملخص EN

We obtain the conditional fault diameter of the k-ary n-cube Interconnection network.

It has been previously shown that under the condition of Forbidden faulty sets (i.e.

assuming each non-faulty node has at least one non-faulty Neighbor), the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected.

We extend this result by showing that the conditional Fault-diameter of the k-ary n-cube is equal to the fault-free diameter plus two.

This means that if there are at most 4n-3 faulty nodes in the k-ary n-cube and if every non-faulty node has at least one non-faulty neighbor, then there exists a fault-free path of length at most the diameter plus two between any two non-faulty nodes.

We also show how to construct these fault-free paths.

With this result the k-ary n-cube joins a group of interconnection Networks (including the hypercube and the star-graph) whose conditional fault diameter has been shown to be only two units over the fault-free diameter.