Non-inclusive g-good-neighbour diagnosability of hypercubes

Abstract

To better measure the fault tolerance and reliability of a network, Yuan et al. introduced the non-inclusive g-good-neighbour diagnosability of a network. The g-good-neighbour faulty set is a special faulty set, which satisfies that every fault-free vertex has at least g fault-free neighbours. The non-inclusive g-good-neighbour diagnosability requires every pair of g-good-neighbour faulty sets is non-inclusive, denoted as $t_{\mathrm{Ng}}(G)$. In this paper, we study the non-inclusive g-good-neighbour diagnosability of hypercubes and obtain $t_{\mathrm{Ng}}(Q_n)=(n-1-g)2^{g+1}+2^g-1$ for $g\in \{1,2\}$ under the PMC model, $t_{N1}(Q_n)=3n-5$, $t_{N2}(Q_n)=8n-21$ under the MM* model.

Keywords:

• Non-inclusive diagnosability
• g-good-neighbour diagnosability
• the PMC model
• the MM* model
• hypercubes

AMS Subject Classifications 2010:

• 05C05
• 05C12
• 05C76

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

All of the material is owned by the authors and/or no permissions are required.

Additional information

Funding

This work is supported by the Science Found of Qinghai Province (No. 2021-ZJ-703), the National Science Foundation of China (Nos. 12261074, 12201335 and 11661068).