Conditional fault-tolerant routing of (n,k)-star graphs

As a generalization of the star graph, the (n,k)-star graph is one of the most important interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant routing problem of (n,k)-star graphs under the conditional fault assumption (CFA), where all the neighbours of any fault-free node cannot be faulty simultaneously. We show that, under the CFA, the (n,k)-star graph can tolerate up to n + k - 4 faulty nodes, and there is a fault-free path of length at most the diameter of the (n,k)-star graph plus 6 between any two fault-free nodes.