Fault diagnosability of regular graphs

Abstract

An interconnection network's diagnosability is an important measure of its self-diagnostic capability. In 2012, Peng et al. proposed a measure for fault diagnosis of the network, namely, the $h$-good-neighbor conditional diagnosability, which requires that every fault-free node has at least $h$ fault-free neighbors. There are two well-known diagnostic models, PMC model and MM* model. The {\it $h$-good-neighbor diagnosability} under the PMC (resp. MM*) model of a graph $G$, denoted by $t_h^{PMC}(G)$ (resp. $t_h^{MM^*}(G)$), is the maximum value of $t$ such that $G$ is $h$-good-neighbor $t$-diagnosable under the PMC (resp. MM*) model. In this paper, we study the $2$-good-neighbor diagnosability of some general $k$-regular $k$-connected graphs $G$ under the PMC model and the MM* model. The main result $t_2^{PMC}(G)=t_2^{MM^*}(G)=g(k-1)-1$ with some acceptable conditions is obtained, where $g$ is the girth of $G$. Furthermore, the following new results under the two models are obtained: $t_2^{PMC}(HS_n)=t_2^{MM^*}(HS_n)=4n-5$ for the hierarchical star network $HS_n$, $t_2^{PMC}(S_n^2)=t_2^{MM^*}(S_n^2)=6n-13$ for the split-star networks $S_n^2$ and $t_2^{PMC}(\Gamma_{n}(\Delta))=t_2^{MM^*}(\Gamma_{n}(\Delta))=6n-16$ for the Cayley graph generated by the $2$-tree $\Gamma_{n}(\Delta)$.

Keywords

• 2-good-neighbor diagnosability; pmc model; mm* model; regular graphs; interconnection networks.