The diagnosability of wheel networks with the condition: 2-extra. (English) Zbl 1537.68019
Summary: Diagnosability is an essential parameter for a multiprocessor system when measuring the reliability of an interconnection network. The \(g\)-extra diagnosability of a system \(G\) denoted by \(\widetilde{t}_g(G)\) was introduced by Zhang et al., which constrains that each fault-free component \(G_i\) owns \(|V(G_i)| \geq g + 1\) fault-free nodes. The \(n\)-dimensional wheel network \(CW_n\) has advantages as a typical topological structure in interconnection networks. The paper establishes the 2-extra diagnosability of \(C W_n\) to be \(6n - 10\) for \(n \geq 6\) when the PMC model and \(\mathrm{MM}^\ast\) model are employed.
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 |
References:
| [1] | Barsi, F.; Grandoni, F.; Maestrini, P., A theory of diagnosability of digital systems, IEEE Trans. Comput., 25, 6, 585-593 (1976) · Zbl 0331.94008 |
| [2] | Dahbura, A.; Masson, G., An \(O( n^{2.5})\) fault identification algorithm for diagnosable systems, IEEE Trans. Comput., 33, 6, 486-492 (1984) · Zbl 0537.68043 |
| [3] | Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 7, 687-692 (2002) |
| [4] | Lai, P.; Tan, J.; Chang, C.; Hsu, L., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175 (2005) |
| [5] | Preparata, F.; Metze, G.; Chien, R., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., EC-16, 6, 848-854 (1967) · Zbl 0189.16904 |
| [6] | 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 |
| [7] | Chang, N.; Hsieh, S., Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst., 25, 11, 3002-3011 (2014) |
| [8] | Lin, C.; Tan, J.; Hsu, L.; Cheng, E.; Lipták, L., Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model, J. Interconnect. Netw., 9, 1-2, 83-97 (2008) |
| [9] | Peng, S.; Lin, C.; Tan, J.; Hsu, L., The g-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 21, 10406-10412 (2012) · Zbl 1247.68032 |
| [10] | Yuan, J.; Liu, A.; Ma, X.; Liu, X.; Qin, X.; Zhang, J., The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM^⁎ model, IEEE Trans. Parallel Distrib. Syst., 26, 4, 1165-1177 (2015) |
| [11] | Guo, J.; Lu, M., Conditional diagnosability of bubble-sort star graphs, Discrete Appl. Math., 201, C, 141-149 (2016) · Zbl 1329.05271 |
| [12] | Hsieh, S.; Kao, C., 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] | Zhou, S.; Wang, J.; Xu, X.; Xu, J., Conditional fault diagnosis of bubble sort graphs under the PMC model, (Intelligence Computation and Evolutionary Computation, vol. 180 (2013)), 53-59 |
| [14] | Hao, R.; Tian, Z.; Xu, J., Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs, Theor. Comput. Sci., 627, 36-53 (2016) · Zbl 1338.68030 |
| [15] | Yuan, J.; Qiao, H.; Liu, A.; Wang, X., Measurement and algorithm for conditional local diagnosis of regular networks under the MM^⁎ model, Discrete Appl. Math., 309, 46-67 (2022) · Zbl 1490.68058 |
| [16] | Wang, M.; Guo, Y.; Wang, S., 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 |
| [17] | Wei, Y.; Xu, M., The 1, 2-good-neighbor conditional diagnosabilities of regular graphs, Appl. Math. Comput., 334, 295-310 (2018) · Zbl 1427.68029 |
| [18] | Feng, W.; Jirimutu; Wang, S., The nature diagnosability of wheel graph networks under the PMC model and MM^⁎ model, Ars Comb., 143, 255-287 (2019) · Zbl 1463.94081 |
| [19] | Feng, W.; Ren, J.; Enhe, C.; Jirimutu; Wang, S., The 2-good-neighbor connectivity of wheel graph networks, Util. Math., 116, 139-167 (2020) · Zbl 1469.05156 |
| [20] | Wang, S.; Yang, Y., 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] | Yuan, J.; Liu, A. X.; Qin, X.; Zhang, J. F.; Li, J., g-good-neighbor conditional diagnosability measure of 3-ary n-cube networks, Theor. Comput. Sci., 626, 144-162 (2016) · Zbl 1336.68018 |
| [22] | Xu, X.; Zhou, S.; Li, J., Reliability of complete cubic networks under the condition of g-good-neighbor, Comput. J., 60, 5, 625-635 (2017) |
| [23] | Guo, J.; Li, D.; Lu, M., The g-good-neighbor conditional diagnosability of the crossed cubes under the PMC and MM^⁎ model, Theor. Comput. Sci., 755, 81-88 (2019) · Zbl 1411.68023 |
| [24] | Hu, X.; Yang, W.; Tian, Y.; Meng, J., Equal relation between g-good-neighbor diagnosability under the PMC model and g-good-neighbor diagnosability under the MM^⁎ model of a graph, Discrete Appl. Math., 262, 96-103 (2019) · Zbl 1411.05242 |
| [25] | Lin, S.; Zhang, W., The 1-good-neighbor diagnosability of unidirectional hypercubes under the PMC model, Appl. Math. Comput., 375, 15, Article 125091 pp. (2020) |
| [26] | Lin, Y.; Lin, L.; Huang, Y.; Wang, J., The \(t / s\)-diagnosability and \(t / s\)-diagnosis algorithm of folded hypercube under the PMC/MM^⁎ model, Theor. Comput. Sci., 887, 85-98 (2021) · Zbl 1514.68017 |
| [27] | Zhang, S.; Yang, W., The g-extra conditional diagnosability and sequential \(t / k\)-diagnosability of hypercubes, Int. J. Comput. Math., 93, 3, 482-497 (2016) · Zbl 1358.68047 |
| [28] | Li, L.; Zhang, X.; Zhu, Q.; Bai, Y., The 3-extra conditional diagnosability of balanced hypercubes under MM^⁎ model, Discrete Appl. Math., 309, 310-316 (2022) · Zbl 1490.68055 |
| [29] | Wang, S., The diagnosability of Möbius cubes for the g-extra condition, Theor. Comput. Sci., 908, 76-88 (2022) · Zbl 1533.68017 |
| [30] | Wang, S.; Wang, Z.; Wang, M., The 2-extra connectivity and 2-diagnosability of Bubble-sort star graph networks, Comput. J., 59, 12, 1839-1856 (2016) |
| [31] | Wang, S.; Ma, X., The g-extra connectivity and diagnosability of crossed cubes, Appl. Math. Comput., 336, 60-66 (2018) · Zbl 1427.68028 |
| [32] | Liu, A.; Wang, S.; Yuan, J.; Li, J., On g-extra conditional diagnosability of hypercubes and folded hypercubes, Theor. Comput. Sci., 704, 62-73 (2017) · Zbl 1382.68037 |
| [33] | Ren, Y.; Wang, S., The tightly super 2-extra connectivity and 2-extra diagnosability of locally twisted cubes, J. Interconnect. Netw., 17, 2, Article 1750006 pp. (2017) |
| [34] | Liu, J.; Zhou, S.; Gu, Z.; Zhou, Q.; Wang, D., Fault diagnosability of Bicube networks under the PMC diagnostic model, Theor. Comput. Sci., 851, 14-23 (2021) · Zbl 1477.68039 |
| [35] | Huang, Y.; Lin, L.; Xu, L., A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM^⁎ model, Theor. Comput. Sci., 828-829, 70-80 (2020) · Zbl 1443.68032 |
| [36] | Feng, W.; Wang, S., The 2-extra connectivity of wheel graph networks, Math. Probl. Eng., 2020, 1-5 (2020) |
| [37] | Feng, W.; Wang, S., Structure connectivity and substructure connectivity of wheel networks, Theor. Comput. Sci., 850, 20-29 (2021) · Zbl 1464.68284 |
| [38] | Fàbrega, J.; Fiol, M., On the extraconnectivity of graphs, Discrete Math., 155, 1-3, 49-57 (1996) · Zbl 0857.05064 |
| [39] | Bondy, J.; Murty, U., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001 |
| [40] | Sengupta, A.; Dahbura, A., On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396 (1992) · Zbl 1395.68062 |
| [41] | Hungerford, T., Algebra (1974), Springer-Verlag: Springer-Verlag New York · Zbl 0293.12001 |
| [42] | Wang, M.; Yang, W.; Guo, Y.; Wang, S., Conditional fault tolerance in a class of Cayley graphs, Int. J. Comput. Math., 93, 1, 67-82 (2016) · Zbl 1338.05124 |
| [43] | Akers, S.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [44] | Chou, Z.; Hsu, C.; Sheu, J., Bubble-sort star graphs: a new interconnection network, (Proceedings of the International Conference on Parallel and Distributed Systems (1996)), 41-48 |
| [45] | Shi, H.; Lu, J., On conjectures of interconnection networks, Comput. Eng. Appl., 44, 31, 112-115 (2008) |
| [46] | Hou, F., Some New Results of the Wheel Networks and Bubble-Sort Star Networks (2013), Northwest Normal University |
| [47] | Cai, H.; Liu, H.; Lu, M., Fault-tolerant maximal local-connectivity on Bubble-sort star graphs, Discrete Appl. Math., 181, 33-40 (2015) · Zbl 1304.05085 |
| [48] | Bauer, D.; Boesch, F.; Suffel, C.; Tindell, R., Connectivity extremal problems and the design of reliable probabilistic networks, (Alavi, Y.; Chartrand, G., The Theory and Application of Graphs (1981), Wiley: Wiley New York), 89-98 · Zbl 0469.05044 |
| [49] | Cheng, E.; Lipman, M.; Park, H., Super connectivity of star graphs, alternating group graphs and split-stars, Ars Comb., 59, 107-116 (2001) · Zbl 1066.68003 |
| [50] | Feng, W.; Ren, J.; Jirimutu; Wang, S., The 2-good-neighbor diagnosability of wheel graph networks under the PMC and MM^⁎ model, Util. Math., 113, 51-68 (2019) · Zbl 1473.68026 |
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.
