World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The g-Extra Conditional Diagnosability of Graphs in Terms of g-Extra Connectivity

    This article is part of the issue:

    The g-extra conditional diagnosability and g-extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault tolerance in a multiprocessor system. The g-extra conditional diagnosability tg̃(G) of graph G is defined as the diagnosability of a multiprocessor system under the assumption that every fault-free component contains more than g vertices. While the g-extra connectivity κ̃g(G) of graph G is the minimum number k for which there is a vertex cut F with |F|=k such that every component of GF has more than g vertices. In this paper, we study the g-extra conditional diagnosability of graph G in terms of its g-extra connectivity, and show that tg̃(G)=κ̃g(G)+g under the MM* model with some acceptable conditions. As applications, the g-extra conditional diagnosability is determined for some BC networks such as hypercubes, varietal hypercubes, and k-ary n-cubes under the MM* model.

    References

    • 1. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (The Macmillan Press Ltd., New York, 1976). CrossrefGoogle Scholar
    • 2. N. W. Chang and S. Y. Hsieh, {2,3}-Extraconnectivities of hypercube-like networks, J. Comput. Syst. Sci. 79 (2013) 669–688. Crossref, ISIGoogle Scholar
    • 3. C. A. Chen and S. Y. Hsieh, (t, k)-diagnosis for component-composition graphs under the MM* model, IEEE Trans. Comput. 60(12) (2011) 1704–1717. Crossref, ISIGoogle Scholar
    • 4. Y. C. Chen and J. J. M. Tan, Restricted connectivity for three families of interconnection networks, Appl. Math. Comput. 188 (2007) 1848–1855. Crossref, ISIGoogle Scholar
    • 5. K. Day, The conditional node connectivity of the k-ary n-cube, J. Inter. Net. 5 (2004) 13–26. LinkGoogle Scholar
    • 6. J. Fàbrega and M. A. Fiol, On the extraconnectivity of graphs, Discr. Math. 155 (1996) 49–57. Crossref, ISIGoogle Scholar
    • 7. J. Fan and L. He, BC interconnection networks and their properties, Chinese J. Computers 26(1) (2003) 84–90. Google Scholar
    • 8. M. Gu and R. Hao, 3-extra connectivity of 3-ary n-cube networks, Info. Proce. Lett. 114 (2014) 486–491. Crossref, ISIGoogle Scholar
    • 9. F. Harary, Conditional connectivity, Networks 13 (1983) 346–357. Crossref, ISIGoogle Scholar
    • 10. G. H. Hsu, F. Chiang, L. M. Shih, L. H. Hsu and J. M. Tan, Conditional diagnosability of hypercubes under the comparison diagnosis model, J. Syst. Arch. 55(2) (2009) 140–146. Crossref, ISIGoogle Scholar
    • 11. Y. Z. Huang, L. M. Lin and L. Xu, 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. CrossrefGoogle Scholar
    • 12. S. Y. Hsieh and Y. H. Chang, Extraconnectivity of k-ary n-cube networks, Theor. Comput. Sci. 443 (2012) 63–69. Crossref, ISIGoogle Scholar
    • 13. P.-L. Lai, J. J. M. Tan, C.-P. Chang and L.-H. Hsu, Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput. 54(2) (2005) 165–175. Crossref, ISIGoogle Scholar
    • 14. A. X. Liu, S. Y. Wang, J. Yuan and J. Li, On g-extra conditional diagnosability of hypercubes and folded hypercubes, Theor. Comput. Sci. 704 (2017) 62–73. Crossref, ISIGoogle Scholar
    • 15. A. X. Liu, S. Y. Wang, J. Yuan and X. Ma, The h-extra connectivity of k-ary n-cubes, Theor. Comput. Sci. 784 (2019) 21–45. Crossref, ISIGoogle Scholar
    • 16. J. Maeng and M. Malek, 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. S. L. Peng, C. K. Lin, J. J. M. Tan and L. H. Hsu, The g-good-neighbor conditional diagnosability of hypercube under the PMC model, Appl. Math. Comput. 218(21) (2012) 10406–10412. Crossref, ISIGoogle Scholar
    • 18. F. P. Preparata, G. Metze and R. T. Chien, On the connection assignment problem of diagnosis systems, IEEE Trans. Electron. Comput. EC-16(6) (1967) 848–854. CrossrefGoogle Scholar
    • 19. A. Sengupta and A. Dahbura, On self-diagnosable multiprocessor system: Diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992) 1386–1396. Crossref, ISIGoogle 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. S. Wang, Z. Wang and M. Wang, The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, Comput. J. 59(12) (2016) 1839–1856. Crossref, ISIGoogle Scholar
    • 22. S. Wang and M. Wang, The g-good-neighbor and g-extra diagnosability of networks, Theor. Comput. Sci. 773 (2019) 107–114. Crossref, ISIGoogle Scholar
    • 23. S. Y. Wang and Y. X. Yang, 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. ISIGoogle Scholar
    • 24. J. M. Xu, Combination of Network Theory (Science Press, Beijing, 2013). Google Scholar
    • 25. W. H. Yang and J. X. Meng, Generalized measures of fault tolerance in hypercube networks, Appl. Math. Lett. 25(10) (2012) 1335–1339. Crossref, ISIGoogle Scholar
    • 26. W. H. Yang and H. Q. Lin, Reliability evaluation of BC networks in terms of the extra vertex- and edge-connectivity, IEEE Trans. Comput. 63(10) (2014) 2540–2548. Crossref, ISIGoogle Scholar
    • 27. J. Yuan, A. X. Liu, X. Ma et al., 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, ISIGoogle Scholar
    • 28. S. R. Zhang and W. H. Yang, The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes, Int. J. Comput. Math. 93(3) (2016) 482–497. Crossref, ISIGoogle Scholar
    • 29. J. X. Zhou, On g-extra connectivity of hypercube-like networks, J. Comput. Syst. Sci. 88 (2017) 208–219. Crossref, ISIGoogle 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