The Non-Inclusive Diagnosability of Regular Graphs

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 tN(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t_N(G)$$\end{document}), 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∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {MM}^*$$\end{document} 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∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {MM}^*$$\end{document} model.