TY - JOUR

T1 - An Analysis on the Reliability of the Alternating Group Graph

AU - Lin, Limei

AU - Huang, Yanze

AU - Lin, Yuhang

AU - Xu, Li

AU - Hsieh, Sun Yuan

N1 - Publisher Copyright:
© 1963-2012 IEEE.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - For interconnection network losing processors, usually, when the surviving network has a large connected component, it can be used as a functional subsystem without leading to severe performance degradation. Consequently, it is crucial to characterize the interprocessor communication ability and efficiency of the surviving structure. In this article, we prove that when a subset D of at most 6n-17 processors is deleted from an n-dimensional alternating group graph AG n, there exists a largest component with cardinality greater or equal to |V(AGn)|-|D|-3 for n\≥ 6 in the remaining network, and the union of small components is, first, an empty graph; or, second, a 3-cycle, or an edge, or a 2-path, or a singleton; or, third, an edge and a singleton, or two singletons. Then, we prove that when a subset D of at most 8n-25 processors is deleted from AG n, there exists a largest component with cardinality greater or equal to |V(AG_n)|-|D|-5 for n\≥ 6 in the remaining network, and the union of small components is, first, an empty graph; or, second, a 5-cycle, or a 4-path, or a 4-claw, or a 4-cycle, or a 3-path, or a 3-claw, or a 3-cycle, or a 2-path, or an edge, or a singleton; or, third, a 4-cycle and a singleton, or a 3-path and a singleton, or a 3-claw and a singleton, or a 2-path and a singleton, two edges, an edge and a singleton, or two singletons; or, fourth, two edges and a singleton, or a 2-path and two singletons, or an edge and two singletons, or three singletons.

AB - For interconnection network losing processors, usually, when the surviving network has a large connected component, it can be used as a functional subsystem without leading to severe performance degradation. Consequently, it is crucial to characterize the interprocessor communication ability and efficiency of the surviving structure. In this article, we prove that when a subset D of at most 6n-17 processors is deleted from an n-dimensional alternating group graph AG n, there exists a largest component with cardinality greater or equal to |V(AGn)|-|D|-3 for n\≥ 6 in the remaining network, and the union of small components is, first, an empty graph; or, second, a 3-cycle, or an edge, or a 2-path, or a singleton; or, third, an edge and a singleton, or two singletons. Then, we prove that when a subset D of at most 8n-25 processors is deleted from AG n, there exists a largest component with cardinality greater or equal to |V(AG_n)|-|D|-5 for n\≥ 6 in the remaining network, and the union of small components is, first, an empty graph; or, second, a 5-cycle, or a 4-path, or a 4-claw, or a 4-cycle, or a 3-path, or a 3-claw, or a 3-cycle, or a 2-path, or an edge, or a singleton; or, third, a 4-cycle and a singleton, or a 3-path and a singleton, or a 3-claw and a singleton, or a 2-path and a singleton, two edges, an edge and a singleton, or two singletons; or, fourth, two edges and a singleton, or a 2-path and two singletons, or an edge and two singletons, or three singletons.

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

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

U2 - 10.1109/TR.2021.3066185

DO - 10.1109/TR.2021.3066185

M3 - Article

AN - SCOPUS:85104261382

SN - 0018-9529

VL - 70

SP - 1542

EP - 1555

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

IS - 4

ER -