Component Reliability Evaluation on Split-Stars

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 S2n, in terms of this metric. We prove that when an arbitrary subset of vertices D with |D| ≤ 6n-15 is removed from S2n, the remaining network will have at most 3 components, with the largest component having at least n! - |D| -3 vertices. With |D| ≤ 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 S2n 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 S2n by considering the minimal neighbor edge-set of appropriate substructures in S2n.

Keywords

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