The \(g\)-good-neighbor diagnosability of locally twisted cubes. (English) Zbl 1379.68024
Summary: Diagnosability of a multiprocessor system is one important measure of the reliability of interconnection networks. In [Appl. Math. Comput. 218, No. 21, 10406–10412 (2012; Zbl 1247.68032)], S.-L. Peng et al. proposed the \(g\)-good-neighbor diagnosability that restrains every fault-free node containing at least \(g\) fault-free neighbors. The locally twisted cube \(L T Q_n\) is applied widely. In this paper, we give that the \(g\)-good-neighbor diagnosability of \(L T Q_n\) is \(2^g(n - g + 1) - 1\) under the PMC model and the \(\mathrm{MM}^{\ast}\) model for \(n \geq 3\) and \(0 \leq g \leq n - 3\).
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 |
Citations:
Zbl 1247.68032References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001 |
| [2] | 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 |
| [3] | Fan, Jianxi, Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 10, 1099-1104 (2002) |
| [5] | Hsieh, Sun-Yuan; Tu, Chang-Jen, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoret. Comput. Sci., 410, 8-10, 926-932 (2009) · Zbl 1162.68046 |
| [6] | Hsieh, Sun-Yuan; Wu, Chang-Yu, Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults, J. Comb. Optim., 19, 1, 16-30 (2010) · Zbl 1185.90029 |
| [7] | 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) |
| [8] | Lee, Chia-Wei; Hsieh, Sun-Yuan, Diagnosability of multiprocessor systems, (Scalable Computing and Communications: Theory and Practice (2013), Wiley) |
| [9] | Liu, Xiuli; Yuan, Jun; Ma, Xue, The \(g\)-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model, J. Taiyuan Univ. Sci. Technol., 35, 5, 390-393 (2014), (in Chinese) |
| [10] | Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessor systems, (Proceeding of 11th International Symposium on Fault-Tolerant Computing (1981)), 173-175 |
| [11] | 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 |
| [12] | 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 |
| [13] | Ren, Yunxia; Wang, Shiying, The 1-good-neighbor connectivity and diagnosability of locally twisted cubes, Chinese Quart. J. Math. (2017), in press · Zbl 1379.68024 |
| [14] | Sengupta, A.; Dahbura, A. T., On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396 (1992) · Zbl 1395.68062 |
| [15] | Wang, Mujiangshan; Guo, Yubao; Wang, Shiying, The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and \(MM^⁎\) model, Int. J. Comput. Math., 94, 3, 620-631 (2017) · Zbl 1362.05062 |
| [16] | Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying, The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and \(MM^⁎\) model, Theoret. Comput. Sci., 628, 92-100 (2016) · Zbl 1338.68036 |
| [17] | Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying, The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs, Discrete Appl. Math. (2017) · Zbl 1379.05056 |
| [18] | Wang, Shiying; Han, Weiping, The \(g\)-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM* model, Inform. Process. Lett., 116, 574-577 (2016) · Zbl 1357.68016 |
| [19] | Wang, Shiying; Wang, Zhenhua; Wang, Mujiangshan, The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks, Discrete Appl. Math., 217, 691-706 (2017) · Zbl 1358.05267 |
| [20] | Wang, Shiying; Yang, Yuxing, The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model, Appl. Math. Comput., 305, 241-250 (2017) · Zbl 1409.68050 |
| [21] | Wei, Chia-Chen; Hsieh, Sun-Yuan, \(h\)-restricted connectivity of locally twisted cubes, Discrete Appl. Math., 217, 330-339 (2017) · Zbl 1358.05168 |
| [22] | Xu, Xiang; Zhou, Shuming; Li, Jinqiang, Reliability of complete cubic networks under the condition of \(g\)-good-neighbor, Comput. J., 60, 5, 625-635 (2017) |
| [23] | Yang, Xiaofan; Evans, David J.; Megson, Graham M., The locally twisted cubes, Int. J. Comput. Math., 82, 4, 401-413 (2005) · Zbl 1097.68522 |
| [24] | 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) |
| [25] | 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 |
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.
