The $g$-good neighbour diagnosability of hierarchical cubic networks

Abstract

Let $G=(V,E)$ be a connected graph, a subset $S\subseteq V(G)$ is called an $R^g$-vertex-cut of $G$ if $G-F$ is disconnected and any vertex in $G-F$ has at least $g$ neighbours in $G-F$. The $R^g$-vertex-connectivity is the size of the minimum $R^g$-vertex-cut and denoted by ${\kappa }^g(G)$. Many large-scale multiprocessor or multi-computer systems take interconnection networks as underlying topologies. Fault diagnosis is especially important to identify fault tolerability of such systems. The $g$-good-neighbor diagnosability such that every fault-free node has at least $g$ fault-free neighbors is a novel measure of diagnosability. In this paper, we show that the $g$-good-neighbor diagnosability of the hierarchical cubic networks $HC{N}_n$ under the PMC model for $1\le g\le n-1$ and the $M{M}^{\ast }$ model for $1\le g\le n-1$ is $2^g(n+2-g)-1$, respectively.