<i>g</i>-Good-Neighbor Conditional Diagnosability and <i>g</i>-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model

Fault diagnosis plays a very important role in maintaining the reliability of multiprocessor systems,and the diagno-sability is an important measure of the diagnosis capability of the system.Except for the traditional diagnosability,there are also conditional diagnosability,such as <i>g</i>-good-neighbor conditional diagnosability,<i>g</i>-extra conditional diagnosability,etc.Where <i>g</i>-good-neighbor conditional diagnosability is defined under the condition that every fault-free vertex has at least <i>g</i> fault-free neighbors,and <i>g</i>-extra conditional diagnosability is defined under the condition that every fault-free component contains more than <i>g</i> vertices.Fault diagnosis needs to be performed under a specific diagnosis model,such as PMC model,symmetric PMC model,in which the symmetric PMC model is a new diagnosis model proposed by adding two assumptions to the PMC model.The <i>n</i>-dimensional hypercube has many excellent properties,so it has been widely studied by researchers.At present,there are a number of diagnosability studies under the PMC models,but there is a lack of diagnosability studies under the symmetric PMC models.This paper first investigates the upper and lower bounds for the <i>g</i>-good-neighbor conditional diagnosability of hypercubes under the symmetric PMC model,with an upper bound of <i>2^g+1(n－g－1)+2^g－1</i> when <i>n≥4</i> and <i>0≤g≤n－4</i> and a lower bound of <i>(2n－2^g+1+1)2^g－1+(n－g)2^g－1－1</i> when <i>g≥0</i> and <i>n≥</i>max<i>{g+4,2^g+1－2^－g－g－1}</i>.Also study the upper and lower bounds for the <i>g</i>-extra conditional diagnosability of hypercubes under the symmetric PMC model,the upper bound is <i>2n(g+1)－5g－2C²_g－2</i> when <i>n≥4</i> and <i>0≤g≤n－4</i>,and the lower bound is$\frac{3}{2} n(g+1)-g-\frac{5}{2} C_{g+1}^{2}-1$ when <i>n≥4</i> and $0 \leqslant g \leqslant \min \left\{n-4,\left\lfloor\frac{2}{3} n\right\rfloor\right\}$.Finally,the correctness of the relevant theoretical conclusions is verified by simulation experiments.