Strong Reliability of Star Graphs Interconnection Networks
Limei Lin, Yanze Huang, Sun‐Yuan Hsieh, Li Xu · IEEE Transactions on Reliability · 2020
For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set$M$of at most$3n-7$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-3$. We then prove that when a set$M$of at most$4n-9$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-5$. Finally, we also calculate the$r$-component connectivity of the$n$-star graph for$2\leq r\leq 5$.