TY - JOUR

T1 - Strong Reliability of Star Graphs Interconnection Networks

AU - Lin, Limei

AU - Huang, Yanze

AU - Hsieh, Sun Yuan

AU - Xu, Li

N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 61702100, Grant U1905211, Grant 61702103, and Grant 61771140, and in part by Fok Ying Tung Education Foundation under Grant 171061.
Publisher Copyright:
© 1963-2012 IEEE.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - 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 ≤q r ≤q 5.

AB - 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 ≤q r ≤q 5.

UR - http://www.scopus.com/inward/record.url?scp=85091280871&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85091280871&partnerID=8YFLogxK

U2 - 10.1109/TR.2020.3013158

DO - 10.1109/TR.2020.3013158

M3 - Article

AN - SCOPUS:85091280871

VL - 71

SP - 1241

EP - 1254

JO - IRE Transactions on Reliability and Quality Control

JF - IRE Transactions on Reliability and Quality Control

SN - 0018-9529

IS - 3

ER -