×

Vulnerability analysis of multiprocessor system based on burnt pancake networks. (English) Zbl 1542.68020

Summary: 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 \(5 n - 9\) in the burnt pancake network \(B P_n ( n \geq 5 )\), \(B P_n \setminus X\) has the largest component \(C\) with \(| C | \geq | V ( B P_n ) | - | X | - 4\) vertices, and all small components present the following structures: (a) an empty graph; (b) one 3-path, one \(K_{1 , 3}\), one \(K_{1 , 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 \(B P_n\) is \(c \kappa_6 ( B P_n ) = 5 n - 6\) for \(n \geq 5\).

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI

References:

[1] Blanco, S. A.; Buehrle, C.; Patidar, A., Cycles in the burnt pancake graph, Discrete Appl. Math., 271, 1-14 (2019) · Zbl 1428.05129
[2] Chang, N.-W.; Deng, W.-H.; Hsieh, S.-Y., Conditional diagnosability of \(( n , K )\)-star networks under the comparison diagnosis model, IEEE Trans. Reliab., 64, 1, 132-143 (2015)
[3] Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of augmented cubes under the PMC model, IEEE Trans. Dependable Secur. Comput., 9, 46-60 (2012)
[4] Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of \(( n , K )\)-star graphs under the PMC model, IEEE Trans. Dependable Secur. Comput., 15, 2, 207-216 (2018)
[5] Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of alternating group networks under the PMC model, IEEE/ACM Trans. Netw., 28, 5, 1968-1980 (2020)
[6] Chang, J.-M.; Pai, K.-J.; Wu, R.-Y.; Yang, J.-S., The 4-component connectivity of alternating group networks, Theor. Comput. Sci., 766, 38-45 (2019) · Zbl 1417.68150
[7] Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-49 (1979) · Zbl 0397.68062
[8] Gu, M.-M.; Hao, R.-X.; Chang, J.-M., Measuring the vulnerability of alternating group graphs and split-star networks in terms of component connectivity, IEEE Access, 7, 97745-97759 (2019)
[9] Gu, M.-M.; Hao, R.-X.; Tang, S.-M.; Chang, J.-M., Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs, Discrete Appl. Math., 279, 80-91 (2020) · Zbl 1439.05126
[10] Guo, J.; Lu, M., Conditional diagnosability of the round matching composition networks, Theor. Comput. Sci., 657, 163-172 (2017) · Zbl 1355.68025
[11] Hoffman, C. M., Group Theoretic Algorithm and Graph Isomorphism (1982), Springer Verlag: Springer Verlag New York · Zbl 0487.68055
[12] Hsieh, S.-Y.; Kao, C.-Y., The conditional diagnosability of \(k\)-ary \(n\)-cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843 (2013) · Zbl 1365.68085
[13] Hu, X.; Liu, H., The (conditional) matching preclusion for burnt pancake graphs, Discrete Appl. Math., 161, 1481-1489 (2013) · Zbl 1287.05117
[14] Lai, Y.-L.; Yu, D.-C.; Hsu, L.-H., Mutually independent hamiltonian cycle of burnt pancake graphs, IEICE Trans. Fund. Electr. Commun. Comput. Sci., 94-A, 1553-1557 (2011)
[15] Li, P.; Xu, M., The largest component of faulty star graphs, Theor. Comput. Sci., 824-825, 57-66 (2020) · Zbl 1448.05118
[16] Lin, L.; Huang, Y.; Hsieh, S.-Y.; Xu, L., Strong reliability of star graphs interconnection networks, IEEE Trans. Reliab. (2020)
[17] Lin, L.; Huang, Y.; Lin, Y.; Xu, L.; Hsieh, S.-Y., An analysis on the reliability of the alternating group graph, IEEE Trans. Reliab. (2021)
[18] Song, S.; Li, X.; Zhou, S.; Chen, M., Fault tolerance and diagnosability of burnt pancake networks under the comparison model, Theor. Comput. Sci., 582, 48-59 (2015) · Zbl 1309.68021
[19] Song, S.; Zhou, S.; Li, X., Conditional diagnosability of burnt pancake networks under the PMC model, Comput. J., 59, 91-105 (2016)
[20] Subinur, D.; Sabir, E.; Meng, J., Star structure connectivities of pancake graphs and burnt pancake graphs, Int. J. Parallel Emergent Distrib. Syst., 36, 5, 440-448 (2021)
[21] Xu, J.-M., Combinatorial Theory in Networks (2013), Science Press: Science Press Beijing
[22] Yang, X.; Evans, D. J.; Chen, B.; Megson, G. M.; Lai, H., On the maximal connected component of hypercube with faulty vertices, Int. J. Comput. Math., 81, 515-525 (2004) · Zbl 1090.68007
[23] Yang, X.; Evans, D. J.; Megson, G. M., On the maximal connected component of hypercube with faulty vertices II, Int. J. Comput. Math., 81, 1175-1185 (2004) · Zbl 1099.68013
[24] Yang, Y.-C.; Kao, S.-S.; Klasing, R.; Hsieh, S.-Y.; Chou, H.-H.; Chang, J.-M., The construction of multiple independent spanning trees on burnt pancake networks, IEEE Access, 9, 16679-16691 (2021)
[25] Zhou, S.; Xiao, W., Conditional diagnosability of alternating group networks, Inf. Process. Lett., 110, 403-409 (2010) · Zbl 1229.68011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.