The g-Extra Conditional Diagnosability of Graphs in Terms of g-Extra Connectivity
Abstract
The -extra conditional diagnosability and -extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault tolerance in a multiprocessor system. The -extra conditional diagnosability of graph is defined as the diagnosability of a multiprocessor system under the assumption that every fault-free component contains more than vertices. While the -extra connectivity of graph is the minimum number for which there is a vertex cut with such that every component of has more than vertices. In this paper, we study the -extra conditional diagnosability of graph in terms of its -extra connectivity, and show that under the MM* model with some acceptable conditions. As applications, the -extra conditional diagnosability is determined for some BC networks such as hypercubes, varietal hypercubes, and -ary -cubes under the MM* model.
References
- 1. , Graph Theory with Applications (The Macmillan Press Ltd., New York, 1976). Crossref, Google Scholar
- 2. , -Extraconnectivities of hypercube-like networks, J. Comput. Syst. Sci. 79 (2013) 669–688. Crossref, ISI, Google Scholar
- 3. , (t, k)-diagnosis for component-composition graphs under the MM* model, IEEE Trans. Comput. 60(12) (2011) 1704–1717. Crossref, ISI, Google Scholar
- 4. , Restricted connectivity for three families of interconnection networks, Appl. Math. Comput. 188 (2007) 1848–1855. Crossref, ISI, Google Scholar
- 5. , The conditional node connectivity of the k-ary n-cube, J. Inter. Net. 5 (2004) 13–26. Link, Google Scholar
- 6. , On the extraconnectivity of graphs, Discr. Math. 155 (1996) 49–57. Crossref, ISI, Google Scholar
- 7. , BC interconnection networks and their properties, Chinese J. Computers 26(1) (2003) 84–90. Google Scholar
- 8. , 3-extra connectivity of 3-ary n-cube networks, Info. Proce. Lett. 114 (2014) 486–491. Crossref, ISI, Google Scholar
- 9. , Conditional connectivity, Networks 13 (1983) 346–357. Crossref, ISI, Google Scholar
- 10. , Conditional diagnosability of hypercubes under the comparison diagnosis model, J. Syst. Arch. 55(2) (2009) 140–146. Crossref, ISI, Google Scholar
- 11. , A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM* model, Theor. Comput. Sci. 828-829(6) (2020) 70–80. Crossref, Google Scholar
- 12. , Extraconnectivity of k-ary n-cube networks, Theor. Comput. Sci. 443 (2012) 63–69. Crossref, ISI, Google Scholar
- 13. , Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput. 54(2) (2005) 165–175. Crossref, ISI, Google Scholar
- 14. , On g-extra conditional diagnosability of hypercubes and folded hypercubes, Theor. Comput. Sci. 704 (2017) 62–73. Crossref, ISI, Google Scholar
- 15. , The h-extra connectivity of k-ary n-cubes, Theor. Comput. Sci. 784 (2019) 21–45. Crossref, ISI, Google Scholar
- 16. , A comparison connection assignment for self-diagnosis of multiprocessor systems, in Proceedings of 11th International Symposium on Fault-Tolerant Computing,
1981 , 173–175. Google Scholar - 17. , The g-good-neighbor conditional diagnosability of hypercube under the PMC model, Appl. Math. Comput. 218(21) (2012) 10406–10412. Crossref, ISI, Google Scholar
- 18. , On the connection assignment problem of diagnosis systems, IEEE Trans. Electron. Comput. EC-16(6) (1967) 848–854. Crossref, Google Scholar
- 19. , On self-diagnosable multiprocessor system: Diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992) 1386–1396. Crossref, ISI, Google Scholar
- 20. TOP500, China’s Tianhe-2 Tops 10 Petaflop/s To Stay Atop TOP500 List (2014), http://top500.org/lists/2014/06/. Google Scholar
- 21. , The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, Comput. J. 59(12) (2016) 1839–1856. Crossref, ISI, Google Scholar
- 22. , The g-good-neighbor and g-extra diagnosability of networks, Theor. Comput. Sci. 773 (2019) 107–114. Crossref, ISI, Google Scholar
- 23. , The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model, Appl. Math. Comput. 305 (2017) 241–250. ISI, Google Scholar
- 24. , Combination of Network Theory (Science Press, Beijing, 2013). Google Scholar
- 25. , Generalized measures of fault tolerance in hypercube networks, Appl. Math. Lett. 25(10) (2012) 1335–1339. Crossref, ISI, Google Scholar
- 26. , Reliability evaluation of BC networks in terms of the extra vertex- and edge-connectivity, IEEE Trans. Comput. 63(10) (2014) 2540–2548. Crossref, ISI, Google Scholar
- 27. , 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) (2015) 1165–1177. Crossref, ISI, Google Scholar
- 28. , The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes, Int. J. Comput. Math. 93(3) (2016) 482–497. Crossref, ISI, Google Scholar
- 29. , On g-extra connectivity of hypercube-like networks, J. Comput. Syst. Sci. 88 (2017) 208–219. Crossref, ISI, Google Scholar
- 30. Q. Zhu, X. K. Wang and J. Ren, Extra connectivity measures of 3-ary n-cubes (2011), arXiv:1105.0991v1 [cs.DM]. Google Scholar


