The Non-Inclusive Diagnosability of Regular Graphs

doi:10.1007/s40305-022-00415-7

Abstract

Abstract: Fault diagnosis is an important area of study with regard to the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, non-inclusive diagnosability (denoted by t_N(G)), was proposed by Ding et al. In this paper, we establish the non-inclusive diagnosability of a class of regular graphs under the PMC model and the MM^* model. As applications, the non-inclusive diagnosabilities of hypercubes, hierarchical hypercubes, folded hypercubes, star graphs, bubble-sort graphs, pancake graphs and dual cubes are determined under the PMC model and the MM^* model.

Key words: PMC model, MM^* model, Regular graph, Fault diagnosability

CLC Number:

68M15

Yu-Long Wei, Tong-Tong Ding, Min Xu. The Non-Inclusive Diagnosability of Regular Graphs[J]. Journal of the Operations Research Society of China, 2023, 11(4): 891-910.

TrendMD

References

[1] Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput. EC-16(6), 848-854 (1967)
[2] Maeng, J., Malek, M.: A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceedings of 11th International Symposium on Fault-Tolerant Computing, pp. 173-175 (1981)
[3] Sengupta, A., Dahbura, A.T.: On self-diagnosable multiprocessor system: diagnosis by the comparison approach. IEEE Trans. Comput. 41(11), 1386-1396 (1992)
[4] Chang, G.Y., Chang, G.J., Chen, G.H.: Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16(4), 314-323 (2005)
[5] Chang, N.W., Hsieh, S.Y.: Structural properties and conditional diagnosability of star graphs by using PMC model. IEEE Trans. Parallel Distrib. Syst. 25(11), 3002-3011 (2014)
[6] Cheng, E., Qiu, K., Shen, Z.: A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks. Theor. Comput. Sci. 757, 56-67 (2019)
[7] Fan, J.X., Lin, X.L.: The t/k-diagnosability of the BC graphs. IEEE Trans. Comput. 54, 176-184 (2005)
[8] Ding, T.T., Xu, M., Zhu, Q.: The non-inclusive diagnosability of hypercubes under the MM* model. Int. J. Found. Comput. Sci. 31(7), 929-940 (2020)
[9] Hao, R.X., Tian, Z.X., Xu, J.M.: Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs. Theor. Comput. Sci. 627, 36-53 (2016)
[10] Hsu, G.H., Tan, J.J.M.: A local diagnosability measure for multiprocessor systems. IEEE Trans. Parall. Distrib. Syst. 18, 598-607 (2007)
[11] Lai, P.L., Tan, J.J.M., Chang, C.P., Hsu, L.H.: Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54(2), 165-175 (2005)
[12] Lee, C.W., Hsieh, S.Y.: Diagnosability of two-matching composition networks under the MM^* model. IEEE Trans. Depend. Secure Comput. 8(2), 246-255 (2011)
[13] Li, X.Y.: Strong diagnosability and conditional diagnosability of optical multi-mesh hypercube networks under the PMC model. Int. J. Comput. Math. 93(12), 2054-2063 (2016)
[14] Lin, L.M., Hsieh, S.Y., Xu, L., Zhou, S.M., Chen, R.Q.: The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model. J. Comput. System Sci. 95, 1-18 (2018)
[15] Peng, S.L., Lin, C.K., Tan, J.J.M., Hsu, L.H.: The g-good-neighbor conditional diagnosability of hypercube under the PMC model. Appl. Math. Comput. 218, 10406-10412 (2012)
[16] Wang, S.Y., Yang, Y.X.: 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)
[17] Wei, Y.L., Xu, M.: Conditional diagnosability of Cayley graphs generated by wheel graphs under the PMC model. Theor. Comput. Sci. 849, 163-172 (2021)
[18] Wei, Y.L., Xu, M.: Hybrid fault diagnosis capability analysis of regular graphs. Theor. Comput. Sci. 760, 1-14 (2019)
[19] Wei, Y.L., Xu, M.: On g-good-neighbor conditional diagnosability of (n, k) -star networks. Theor. Comput. Sci. 697, 79-90 (2017)
[20] Wei, Y.L., Xu, M.: The g-good-neighbor conditional diagnosability of locally twisted cubes. J. Oper. Res. Soc. China 6(2), 333-347 (2018)
[21] Wei, Y.L., Xu, M.: The 1, 2 -good-neighbor conditional diagnosabilities of regular graphs. Appl. Math. Comput. 334, 295-310 (2018)
[22] Xu, M., Thulasiraman, K., Hu, X.D.: Conditional diagnosability of matching composition networks under the PMC model. IEEE Trans. Circuits Syst. II: Express Briefs 56(11), 875-879 (2009)
[23] Xu, M., Thulasiraman, K., Zhu, Q.: Conditional diagnosability of a class of matching composition networks under the comparison model. Theor. Comput. Sci. 674, 43-52 (2017)
[24] Xu, M., Wei, Y.L.: The h-edge tolerable diagnosability of balanced hypercubes. Theor. Comput. Sci. 795, 540-546 (2019)
[25] Yuan, J., Liu, A.X., Ma, 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)
[26] 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)
[27] Zhou, S.M., Chen, L.X., Xu, J.M.: Conditional fault diagnosability of dual-cubes. Internat. J. Found. Comput. Sci. 23(8), 1729-1749 (2012)
[28] Zhou, S.M., Lin, L.M., Xu, J.M.: Conditional fault diagnosis of hierarchical hypercubes. Int. J. Comput. Math. 89(16), 2152-2164 (2012)
[29] Zhu, Q., Guo, G.D., Tang, W.L., Zhang, C.Q.: A diagnosis algorithm by using graph-coloring under the PMC model. J. Comb. Optim. 32, 960-969 (2016)
[30] Zhu, Q., Li, L.L., Liu, S.Y., Zhang, X.: Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM^* model. Theor. Comput. Sci. 758, 1-8 (2019)
[31] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd, New York (1976)
[32] Dahbura, A.T., Masson, G.M.: An O(n^2.5) faulty identification algorithm for diagnosable systems. IEEE Trans. Comput. 33(6), 486-492 (1984)
[33] Saad, Y., Schultz, M.H.: Topological properties of hypercubes. IEEE Trans. Comput. 37(7), 867-872 (1988)
[34] Malluhi, Q.M., Bayoumi, M.A.: The hierarchical hypercube: a new interconnection topology for massively parallel systems. IEEE Trans. Parallel Distrib. Syst. 5(1), 17-30 (1994)
[35] El-Amawy, A., Latifi, S.: Properties and performance of folded hypercubes. IEEE Trans. Parallel Distrib. Syst. 2(1), 31-42 (1991)
[36] Xu, J.M., Ma, M.J.: Cycles in folded hypercubes. Appl. Math. Lett. 19, 140-145 (2006)
[37] Zhu, Q., Xu, J.M., Hou, X.M., Xu, M.: On reliability of the folded hypercubes. Inform. Sci. 177, 1782-1788 (2007)
[38] Akers, S.B., Krishnamurthy, B.: A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38(4), 555-566 (1989)
[39] Kanevsky, A., Feng, C.: On the embedding of cycles in pancake graphs. Parallel Comput. 21, 923-936 (1995)
[40] Li, Y., Peng, S.: Dual-cubes: a new interconnection network for high-performance computer clusters. In: Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture. pp 51-57 (2000)