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

Abstract

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.

Keywords:

• $(n,k)$-star graph
• fault-tolerant routing
• conditional fault
• interconnection network

2010 AMS Subject Classifications:

• 68R10
• 94C15
• 68M10

Disclosure Statement

No potential conflict of interest was reported by the authors.