Reliability evaluation of complete cubic networks

Abstract

Fault diagnostic analysis is extremely important for interconnection networks. Given a graph G and a positive integer g, the g-extra connectivity of G (denoted by ${\kappa }_o^{\left(g\right)}\left(G\right)$) is the minimum cardinality of a subset S of $V\left(G\right)$ such that G−S is disconnected and every remaining component has at least g + 1 vertices. The g-extra diagnosability of G (denoted by ${\tilde{t}}_g\left(G\right)$), is the maximum number of faulty vertices that the system can guarantee to identify under the condition that every fault-free component contains at least g + 1 vertices. The t/k-diagnosis strategy can detect up to t faulty vertices which might include at most k misdiagnosed vertices. In this paper, we first determine ${\kappa }_o^{\left(g\right)}\left(CCN\right(n\left)\right)=(g+1)n-\left(\genfrac{}{}{0em}{}{g+1}{2}\right)+1$ for $n\ge 2$, $1\le g\le n-1$, where $CCN\left(n\right)$ is an n-dimensional complete cubic network, which generalises the hierarchical cubic network. Moreover, we establish ${\tilde{t}}_g\left(CCN\right(n\left)\right)=(g+1)(n+1)-\left(\genfrac{}{}{0em}{}{g+1}{2}\right)$ under the PMC model ($n\ge 4$, $1\le g\le n-3$) and under the MM* model ($n\ge 6$, $1\le g\le \left(n-2\right)/4$), respectively. Furthermore, we show that $CCN\left(n\right)$ is $\left[\right(k+1)n-\left(\genfrac{}{}{0em}{}{k+1}{2}\right)+1]/k$-diagnosable under the PMC model. As a consequence, we also derive the related results of the n-dimensional hierarchical cubic network $HC{N}_n$.

GRAPHICAL ABSTRACT

Keywords:

• g-extra connectivity
• g-extra diagnosability
• t/k-diagnosability
• complete cubic networks

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was partly supported by the National Natural Science Foundation of China (Nos. 61977016, 61572010, 61602118 and 61702100), Natural Science Foundation of Fujian Province (Nos. 2017J01738, 2015J01240 and JAT170118).