The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks. (English) Zbl 1358.05267
Summary: Connectivity plays an important role in measuring the fault tolerance of interconnection networks. The \(g\)-good-neighbor connectivity of an interconnection network \(G\) is the minimum cardinality of \(g\)-good-neighbor cuts. Diagnosability of a multiprocessor system is one important study topic. A new measure for fault diagnosis of the system restrains that every fault-free node has at least \(g\) fault-free neighbor vertices, which is called the \(g\)-good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the \(n\)-dimensional bubble-sort star graph \(\mathrm{BS}_n\) has many good properties. In this paper, we prove that 2-good-neighbor connectivity of \(\mathrm{BS}_n\) is \(8 n - 22\) for \(n \geq 5\) and the 2-good-neighbor connectivity of \(\mathrm{BS}_4\) is 8; the 2-good-neighbor diagnosability of \(\mathrm{BS}_n\) is \(8 n - 19\) under the PMC model and \(\mathrm{MM}^\ast\) model for \(n \geq 5\).
References:
| [1] | Akers, Sheldon B.; Krishnamurthy, Balakrishnan, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Barsi, F.; Grandoni, F.; Maestrini, P., A theory of diagnosability of digital systems, IEEE Trans. Comput., 25, 6, 585-593 (1976) · Zbl 0331.94008 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001 |
| [4] | Cai, Hongyan; Liu, Huiqing; Lu, Mei, Fault-tolerant maximal local-connectivity on bubble-sort star graphs, Discrete Appl. Math., 181, 33-40 (2015) · Zbl 1304.05085 |
| [5] | Chang, Nai-Wen; Cheng, Eddie; Hsieh, Sun-Yuan, Conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model, ACM Trans. Des. Autom. Electron. Syst., 20, 2, 1-16 (2015) |
| [6] | Chang, Nai-Wen; Deng, Wei-Hao; Hsieh, Sun-Yuan, Conditional diagnosability of \((n, k)\)-star networks under the comparison diagnosis model, IEEE Trans. Reliab., 64, 1, 132-143 (2015) |
| [7] | Chang, Nai-Wen; Hsieh, Sun-Yuan, Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst., 25, 11, 3002-3011 (2014) |
| [8] | Dahbura, A. T.; Masson, G. M., An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems, IEEE Trans. Comput., 33, 6, 486-492 (1984) · Zbl 0537.68043 |
| [9] | Day, Khaled; Triphthi, Anand, A comparative study of topological properties of hypercubes and star graphs, IEEE Trans. Parallel Distrib. Syst., 5, 1, 31-38 (1994) |
| [10] | Fan, Jianxi, Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 10, 1099-1104 (2002) |
| [11] | Guo, Jia; Lu, Mei, Conditional diagnosability of bubble-sort star graphs, Discrete Appl. Math., 201, 141-149 (2016) · Zbl 1329.05271 |
| [12] | Hsieh, Sun-Yuan, Embedding longest fault-free paths onto star graphs with more vertex faults, Theoret. Comput. Sci., 337, 1-3, 370-378 (2005) · Zbl 1104.68085 |
| [14] | Huang, Chao-Wen; Huang, Hui-Ling; Hsieh, Sun-Yuan, Edge-bipancyclicity of star graphs with faulty elements, Theoret. Comput. Sci., 412, 6938-6947 (2011) · Zbl 1230.68159 |
| [15] | Hungerford, Thomas W., Algebra (1974), Springer-Verlag: Springer-Verlag New York · Zbl 0293.12001 |
| [16] | Kavianpour, A., Sequential diagnosability of star graphs, J. Comput. Electr. Eng., 22, 1, 37-44 (1996) |
| [17] | Lai, Pao-Lien; Tan, Jimmy J. M.; Chang, Chien-Ping; Hsu, Lih-Hsing, Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175 (2005) |
| [18] | Latifi, Shahram, A study of fault tolerance in star graph, Inform. Process. Lett., 102, 5, 196-200 (2007) · Zbl 1184.68115 |
| [19] | Latifi, Shahram; Saberinia, Ebrahim; Wu, Xiaolong, Robustness of star graph network under link failure, Inform. Sci., 178, 3, 802-806 (2008) · Zbl 1126.68323 |
| [20] | Li, Tseng-Kuei; Tan, Jimmy J. M.; Hsu, Lih-Hsing, Hyper Hamiltonian laceability on edge fault star graph, Inform. Sci., 165, 1-2, 59-71 (2004) · Zbl 1057.05054 |
| [21] | Li, Xiang-Jun; Xu, Jun-Ming, Generalized measures for fault tolerance of star networks, Networks, 63, 3, 225-230 (2014) · Zbl 1387.05131 |
| [22] | Lin, Cheng-Kuan; Tan, Jimmy J. M.; Hsu, Lih-Hsing; Cheng, Eddie; Lipták, László, Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model, J. Interconnect. Netw., 9, 1-2, 83-97 (2008) |
| [23] | Lin, Limei; Xu, Li; Zhou, Shuming, Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model, Theoret. Comput. Sci., 618, 21-29 (2016) · Zbl 1335.68186 |
| [24] | Lin, Limei; Xu, Li; Zhou, Shuming; Hsieh, Sun-Yuan; Extra, The, restricted connectivity and conditional diagnosability of split-star networks, IEEE Trans. Parallel Distrib. Syst., 27, 2, 533-545 (2016) |
| [25] | Lin, Limei; Zhou, Shuming; Xu, Li; Wang, Dajin, The extra connectivity and conditional diagnosability of alternating group networks, IEEE Trans. Parallel Distrib. Syst., 26, 8, 2352-2362 (2015) |
| [27] | Peng, Shao-Lun; Lin, Cheng-Kuan; Tan, Jimmy J. M.; Hsu, Lih-Hsing, The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 21, 10406-10412 (2012) · Zbl 1247.68032 |
| [28] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Comput., EC-16, 848-854 (1967) · Zbl 0189.16904 |
| [29] | Rescigno, A. A., Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security, Inform. Sci., 137, 1-4, 259-276 (2001) · Zbl 0996.68024 |
| [30] | Tsai, Ping-Ying; Fu, Jung-Sheng; Chen, Gen-Huey, Fault-free longest paths in star networks with conditional link faults, Theoret. Comput. Sci., 410, 8-10, 766-775 (2009) · Zbl 1162.68004 |
| [31] | Walker, David; Latifi, Shahram, Improving bounds on link failure tolerance of the star graph, Inform. Sci., 180, 13, 2571-2575 (2010) · Zbl 1211.68293 |
| [32] | Wan, Min; Zhang, Zhao, A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett., 22, 2, 264-267 (2009) · Zbl 1163.05323 |
| [34] | Wang, Shiying; Han, Weiping, The \(g\)-good-neighbor conditional diagnosability of \(n\)-dimensional hypercubes under the \(M M^\ast\) model, Inform. Process. Lett., 116, 574-577 (2016) · Zbl 1357.68016 |
| [35] | Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying, The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and \(M M^\ast\) model, Theoret. Comput. Sci., 628, 92-100 (2016) · Zbl 1338.68036 |
| [37] | Wang, Mujiangshan; Yang, Wenguo; Guo, Yubao; Wang, Shiying, Conditional fault tolerance in a class of Cayley graphs, Int. J. Comput. Math., 3, 1, 67-82 (2016) · Zbl 1338.05124 |
| [39] | Yang, Yuxing; Wang, Shiying, Conditional connectivity of star graph networks under embedding restriction, Inform. Sci., 199, 187-192 (2012) · Zbl 1248.68103 |
| [40] | Yuan, Jun; Liu, Aixia; Ma, Xue; Liu, Xiuli; Qin, Xiao; Zhang, Jifu, The \(g\)-good-neighbor conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC model and \(M M^\ast\) model, IEEE Trans. Parallel Distrib. Syst., 26, 1165-1177 (2015) |
| [41] | Yuan, Jun; Liu, Aixia; Qin, Xiao; Zhang, Jifu; Li, Jing, \(g\)-good-neighbor conditional diagnosability measures for 3-ary n-cube networks, Theoret. Comput. Sci., 622, 144-162 (2016) · Zbl 1336.68018 |
| [42] | Zhang, Shurong; Yang, Weihua, The \(g\)-extra conditional diagnosability and sequential \(t / k\)-diagnosability of hypercubes, Int. J. Comput. Math., 93, 3, 482-497 (2016) · Zbl 1358.68047 |
| [43] | Zheng, Jun; Latifi, Shahram; Regentova, Emma; Luo, Kai; Wu, Xiaolong, Diagnosability of star graphs under the comparison diagnosis model, Inform. Process. Lett., 93, 1, 29-36 (2005) · Zbl 1173.68615 |
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.
