Component reliability evaluation on split-stars

Limei Lin, Yanze Huang, Dajin Wang, Li Xu

Research output: Contribution to journalArticle

Abstract

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}.

Original languageEnglish
Article number8865023
Pages (from-to)147939-147953
Number of pages15
JournalIEEE Access
Volume7
DOIs
StatePublished - 1 Jan 2019

    Fingerprint

Keywords

  • component (edge) connectivity
  • fault tolerance
  • linearly many faults
  • Reliability
  • split-stars

Cite this