Vulnerability analysis of multiprocessor system based on burnt pancake networks

With the large scale network's popularity in different fields, such as cloud computing, privacy protection, social networks and so on, the robustness analysis of networks against faulty processors has recently attracted more attention. When some processors are attacked and lose function, how to characterize the communication ability and efficiency of the surviving network is very crucial. From the viewpoint of graph theory, the size of the maximal component after removing certain faulty vertices can be viewed as a metric of fault tolerability, which is reckoned as an important dimension for the robustness analysis of a network. The h-component connectivity of a network G, denoted by c kappa(h)(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least h components. In this paper, we show that when removing any subset X with order of at most 5n-9 in the burnt pancake network BPn(n >= 5), BPn\X has the largest component C with vertical bar C vertical bar >=vertical bar V(BPn)vertical bar-vertical bar X vertical bar-4 vertices, and all small components present the following structures: (a) an empty graph; (b) one 3-path, one K-1,K-3, one K-1,K-2, or an edge, or an isolated vertex; (c) one K(1,2 )and an edge, one K(1,2 )and an isolated vertex, two edges, one edge and an isolated vertex, or two isolated vertices; (d) an edge and two isolated vertices, or three isolated vertices; (e) four isolated vertices. Besides, we determine that the 6-component connectivity of BPn is c kappa(6)(BPn)=5n-6 for n >= 5. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

With the increasing popularity of large scale networks in various fields, the robustness analysis of networks against faulty processors has become a topic of interest. This paper investigates the size and structure of the surviving network when certain faulty vertices are removed in the burnt pancake network.