TY - JOUR

T1 - Component reliability evaluation on split-stars

AU - Lin, Limei

AU - Huang, Yanze

AU - Wang, Dajin

AU - Xu, Li

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2019

Y1 - 2019

N2 - The failure of some key vertices in a network, due to either attacks or malfunctioning, may break the network into several disconnected components-the vertices within each component are connected, but there are no connections between components. When this happens, two measures should be of concern: (1) the number of components in the remaining network; and (2) the size of each component. When a given number of 'break vertices' are removed from a network, we hope to have as few components as possible in the remaining network. On the other hand, it is certainly desirable that the components are as large as possible. Therefore both the number of components and the size of the maximal component after removing certain vertices can be a metric of a network's fault tolerability, an important dimension of its robustness. In this paper, we examine the split-star, denoted S_{n}^{2} , in terms of this metric. We prove that when an arbitrary subset of vertices D with |D|\leq 6n-15 is removed from S_{n}^{2} , the remaining network will have at most 3 components, with the largest component having at least n!-|D|-3 vertices. With |D|\leq 8n-21 , the remaining network has at most 4 components, with the largest component's size at least n!-|D|-5. As a theoretical application, the r-component connectivity of S_{n}^{2} is estimated by using the obtained maximal component and the minimal neighbor-set of independent set of size r. Moreover, we present a bound of r-component edge connectivity on S_{n}^{2} by considering the minimal neighbor edge-set of appropriate substructures in S_{n}^{2}.

AB - The failure of some key vertices in a network, due to either attacks or malfunctioning, may break the network into several disconnected components-the vertices within each component are connected, but there are no connections between components. When this happens, two measures should be of concern: (1) the number of components in the remaining network; and (2) the size of each component. When a given number of 'break vertices' are removed from a network, we hope to have as few components as possible in the remaining network. On the other hand, it is certainly desirable that the components are as large as possible. Therefore both the number of components and the size of the maximal component after removing certain vertices can be a metric of a network's fault tolerability, an important dimension of its robustness. In this paper, we examine the split-star, denoted S_{n}^{2} , in terms of this metric. We prove that when an arbitrary subset of vertices D with |D|\leq 6n-15 is removed from S_{n}^{2} , the remaining network will have at most 3 components, with the largest component having at least n!-|D|-3 vertices. With |D|\leq 8n-21 , the remaining network has at most 4 components, with the largest component's size at least n!-|D|-5. As a theoretical application, the r-component connectivity of S_{n}^{2} is estimated by using the obtained maximal component and the minimal neighbor-set of independent set of size r. Moreover, we present a bound of r-component edge connectivity on S_{n}^{2} by considering the minimal neighbor edge-set of appropriate substructures in S_{n}^{2}.

KW - Reliability

KW - component (edge) connectivity

KW - fault tolerance

KW - linearly many faults

KW - split-stars

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

U2 - 10.1109/ACCESS.2019.2946705

DO - 10.1109/ACCESS.2019.2946705

M3 - Article

AN - SCOPUS:85077751328

SN - 2169-3536

VL - 7

SP - 147939

EP - 147953

JO - IEEE Access

JF - IEEE Access

M1 - 8865023

ER -