Fault tolerance of (n, k)-Star Graphs
Shuming Zhou, Lanxiang Chen · 2010
The growing size of a multiprocessor system increases its vulnerability to component failures. As the number of faults in the network structure increases, it is desirable that most of the network stays connected, with at most a few processors separated from the rest, since then the network will continue to be able to function. This paper proved that the largest connected component of the survival graph of (n, k)-Star Graph Sn,kcontains almost all the remaining vertices when a lot of faulty vertices occur.