Wanlin Gan¹, Faye Geng¹, He Li^2*
1School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai, China.
²School of Information Engineering, Communication University of Shanxi, Jinzhong, China.
DOI: 10.4236/jamp.2026.141011   PDF    HTML   XML   86 Downloads   273 Views   Citations

Abstract

The diagnosability of interconnection networks serves as a critical metric for evaluating the reliability of multiprocessor systems, as it quantifies the system’s capability to identify faulty processors. Among various diagnosability models, the non-inclusive $g$ -good-neighbor diagnosability offers a more precise characterization of fault tolerance by considering both the non-inclusive nature of fault sets and the requirement of maintaining a certain number of good neighbors for non-faulty vertices. This study focuses on the non-inclusive 1-good-neighbor diagnosability of augmented cubes ($A{Q}_n$ ), a class of interconnection networks with excellent topological properties. Through systematic analysis using structural construction, proof by contradiction, and induction, we derive the exact values of the non-inclusive 1-good-neighbor diagnosability of $A{Q}_n$ under two classic diagnosis models: under the PMC model, $t_{N_1}\left(A{Q}_n\right)=8n-27$ for $n\ge 23$ ; under the MM^* model, $t_{N_1}\left(A{Q}_n\right)=6n-17$ for $n\ge 13$ . These results provide valuable insights for the design and optimization of reliable multiprocessor systems, and lay a foundation for extending the research to $g\ge 2$ or other network topologies.

Keywords

Non-Inclusive Diagnosability, -Good-Neighbor, Augmented Cubes

Share and Cite:

1. Introduction

The exponential growth of data volume and the increasing demand for high-performance computing have driven the rapid development of large-scale parallel processing systems. The interconnection network, as the communication backbone of multiprocessor systems, directly determines the efficiency and reliability of the entire system. Its topology, which describes the connection pattern between processors, plays a pivotal role in influencing system performance such as communication latency and fault tolerance [1] [2]. In practical operations, processor faults are inevitable due to hardware aging, environmental interference, or other factors. Therefore, accurately identifying faulty processors (i.e., fault diagnosis) is essential to ensure the continuous and stable operation of the system [3].

To address the fault diagnosis problem, two classic diagnosis models have been proposed: the PMC model [1] and the MM^* model [2]. The PMC model diagnoses faults through mutual testing between adjacent processors, while the MM^* model relies on comparison-based testing. For these models, two key propositions for distinguishing fault sets have been widely recognized [3] [4]:

Proposition 1. [3] For any two distinct sets $F_1,F_2\subseteq V\left(G\right)$ , $F_1$ and $F_2$ are distinguishable under the PMC model if and only if there exists a vertex $u\in \overline{F_1\cup F_2}$ and there exists a vertex $v\in F_1\Delta F_2$ such that $uv\in E\left(G\right)$ (See Figure 1(a)).

Proposition 2. [4] For any two distinct sets $F_1,F_2\subseteq V\left(G\right)$ , $F_1$ and $F_2$ are distinguishable under the MM^* model if and only if at least one of the following conditions is satisfied (See Figure 1(b)).

Figure 1. Illustration of Propositions 1.1 and 1.2.

(1) There exist three vertices $u\in F_1\Delta F_2$ and $v,w\in \overline{F_1\cup F_2}$ such that $uw,vw\in E\left(G\right)$ .

(2) There exist three vertices $u,v\in F_1-F_2$ and $w\in \overline{F_1\cup F_2}$ such that $uw,vw\in E\left(G\right)$ .

(3) There exist three vertices $u,v\in F_2-F_1$ and $w\in \overline{F_1\cup F_2}$ such that $uw,vw\in E\left(G\right)$ .

In recent years, extensive research has been conducted on the diagnosability of various interconnection networks, including regular networks, matching composition networks, and lexicographic product networks [5]-[9]. As a generalized form of conditional diagnosability, the $g$ -good-neighbor conditional diagnosability requires that each non-faulty vertex retains at least $g$ neighbors within the non-faulty set, which more closely reflects the actual operating conditions of the system [10]. This metric has been applied to analyze the diagnosability of networks such as k-ary n-cubes, star graphs, and locally exchanged twisted cubes [11]-[13].

However, existing studies primarily focus on inclusive fault sets (i.e., one fault set is a subset of the other), while the probability of non-inclusive fault sets (i.e., neither $F_1\subseteq F_2$ nor $F_2\subseteq F_1$ ) cannot be ignored in practical scenarios [14]. To fill this gap, the concept of non-inclusive diagnosability has been proposed, and relevant research has been carried out for networks such as alternating group graphs, hypercubes, and $\left(n,k\right)$ -star networks [15]-[18]. The non-inclusive $g$ -good-neighbor diagnosability, which combines the advantages of non-inclusive fault sets and $g$ -good-neighbor constraints, provides a more comprehensive measure of the system’s diagnosis capability [19]. For instance, in large-scale data centers where processors are geographically distributed across multiple clusters, failures often occur independently due to localized issues such as power outages, cooling system malfunctions, or hardware aging. These failures typically affect separate clusters rather than concentrating around a single vertex’s neighborhood, resulting in fault sets that do not include all neighbors of any vertex. Similarly, in distributed computing networks spanning multiple regions, communication delays or regional network disruptions can lead to simultaneous but isolated failures, forming non-inclusive fault patterns. The non-inclusive $g$ -good-neighbor diagnosability has been studied in interconnection networks, hypercubes [20] [14].

The augmented cube $A{Q}_n$ is a promising interconnection network topology with superior properties such as high connectivity, symmetry, and fault tolerance [21]. Previous studies have investigated the diagnosability of $A{Q}_n$ under different models, and derived results such as its conditional diagnosability and $g$ -good-neighbor conditional diagnosability [22]-[25]. However, the non-inclusive 1-good-neighbor diagnosability of $A{Q}_n$ remains unaddressed. This study aims to fill this research gap by systematically analyzing the structural characteristics of $A{Q}_n$ and deriving the exact values of its non-inclusive 1-good-neighbor diagnosability under the PMC and MM^* models.

2. Preliminaries

For a simple undirected graph $G=\left(V\left(G\right),E\left(G\right)\right)$ , let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and edge set of $G$ , respectively. For a vertex $u\in V\left(G\right)$ , $N_G\left(u\right)$ represents the neighborhood of $u$ (i.e., the set of vertices adjacent to $u$ ), and $d_G\left(u\right)=\left|N_G\left(u\right)\right|$ denotes the degree of $u$ . A graph $G$ is called $k$ -regular if $d_G\left(u\right)=k$ for all $u\in V\left(G\right)$ . A vertex subset $S\subseteq V\left(G\right)$ is referred to as a vertex cut if $G-S$ is disconnected.

The symmetric difference of two sets $F_1$ and $F_2$ is defined as $F_1\Delta F_2=\left(F_1\cup F_2\right)\backslash \left(F_1\cap F_2\right)$ , which consists of elements that belong to exactly one of the two sets. Two sets $F_1$ and $F_2$ are defined as non-inclusive if and only if neither $F_1$ is a subset of $F_2$ nor $F_2$ is contained in $F_1$ , mathematically expressed as $F_1⊈F_2$ and $F_2⊈F_1$ .

Definition 1. [19] A system $G=\left(V,E\right)$ is non-inclusive $g$ -good-neighbor $t$ -diagnosable if and only if $F_1$ and $F_2$ are distinguishable for any two distinct non-inclusive $g$ -good-neighbor faulty subsets $F_1$ and $F_2$ of $V\left(G\right)$ with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ . The non-inclusive $g$ -good-neighbor diagnosability of $G$ , denoted by $t_{Ng}\left(G\right)$ , is the maximum value of the integer $t$ such that $G$ is non-inclusive $g$ -good-neighbor $t$ -diagnosable.

Figure 2. $A{Q}_2$ and $A{Q}_3$ .

Definition 2. [26] $A{Q}_1$ is a complete graph $K_2$ with the vertex set $\left\{0,1\right\}$ . For $n\ge 2$ , $A{Q}_n$ is obtained by taking two copies of the augmented cube $A{Q}_{n-1}$ , denoted by $A{Q}_{n-1}^0$ and $A{Q}_{n-1}^1$ , and adding $2\times 2^{n-1}$ edges between the two as follows:

Let $V\left(A{Q}_{n-1}^0\right)=\left\{0u_{n-1}\cdots u_2{u}_1:u_i=0\text{or}1\right\}$ and $V\left(A{Q}_{n-1}^1\right)=\left\{1u_{n-1}\cdots u_2{u}_1:u_i=0\text{or}1\right\}$ . A vertex $u=0a_{n-1}\cdots a_2{a}_1$ of $V\left(A{Q}_n^0\right)$ is adjacent to $v=1b_{n-1}\cdots b_2{b}_1\in V\left(A{Q}_n^1\right)$ of $A{Q}_{n-1}^1$ if and only if either

(1) $a_i=b_i$ for $1\le i\le n-1$ ; or

(2) $a_i={\overline{b}}_i$ for $1\le i\le n-1$ , where ${\overline{b}}_i=1-b_i$ .

According to Definition 1 of augmented cubes, we write this recursive construction of $A{Q}_n$ symbolically as $A{Q}_n=L\oplus R$ , where $L\cong A{Q}_{n-1}^0$ and $R\cong A{Q}_{n-1}^1$ . We call the edges between $L$ and $R$ crossed edges. Clearly, every vertex of $A{Q}_n$ is incident with two crossed edges. For an $n$ -bit binary string $u=a_n{a}_{n-1}\cdots a_1$ , we use $u_i$ (respectively, ${\overline{u}}_i$ ) to denote the binary string $a_n\cdots {\overline{a}}_i\cdots a_1$ (respectively, $a_n\cdots {\overline{a}}_i\cdots {\overline{a}}_1$ ) which differs with $u$ in the $i$ th bit position (respectively, from the first to the $i$ th bit positions). It is clear that $u_1={\overline{u}}_1$ . We use $u_1$ rather than ${\overline{u}}_1$ [26].

'The augmented cubes AQ₂ and AQ₃ are shown in Figure 2.

An alternative definition of $A{Q}_n$ is given in the following.

Definition 3. [26] The augmented cube $A{Q}_n$ of dimension $n$ has $2^n$ vertices. Each vertex is labeled by a unique $n$ -bit binary string as its address. Two vertices $u=a_n{a}_{n-1}\cdots a_1$ and $v=b_n{b}_{n-1}\cdots b_1$ are joined iff either (1) There exists an integer $i$ , $1\le i\le n$ , such that $v=u_i$ ; in this case, the edge is called a hypercube edge of dimension $i$ , denoted by $\left(u,u_i\right)$ , or (2) There exists an integer $i$ , $2\le i\le n$ , such that $v={\overline{u}}_i$ ; in this case, the edge is called a complement edge of dimension $i$ , denoted by $\left(u,{\overline{u}}_i\right)$ .

Clearly, $A{Q}_n$ is $\left(2n-1\right)$ -regular. From the definition of $A{Q}_n$ , we have the useful properties as follows.

Lemma 3. [27] Let a cycle of four nodes $\left\{u,v,x,y\right\}$ in $A{Q}_n$ , where $v={\overline{u}}_2$ , $x={\overline{u}}_4$ , and $y={\overline{x}}_2$ . $\left|N\left(\left\{u,v,x,y\right\}\right)\right|=8n-28$ for $n\ge 5$ .

Lemma 4. [26] Any two vertices in $A{Q}_n$ have at most four common neighbors for $n\ge 3$ .

Lemma 5 [28] Let $X$ be a vertex set of $A{Q}_n$ ($n\ge 2$ ).

1) If $\left|X\right|=2$ , then $\left|N\left(X\right)\right|\ge 4n-8$ ,

2) If $\left|X\right|=3$ , then $\left|N\left(X\right)\right|\ge 6n-17$ ,

3) If $\left|X\right|=4$ , then $\left|N\left(X\right)\right|\ge 8n-28$ ,

4) If $\left|X\right|=5$ , then $\left|N\left(X\right)\right|\ge 10n-31$ .

Lemma 6. [27] Let $F$ be a vertices set of $A{Q}_n$ , $\left|F\right|\le 6n-18$ for $n\ge 4$ , $A{Q}_n-F$ is either connected, or it consists of a large component, and all the small components contain at most 2 vertices.

Lemma 7. [28] Let $F$ be a vertices set of $A{Q}_n$ , $\left|F\right|\le 8n-42$ for $n\ge 8$ , $A{Q}_n-F$ is either connected, or it consists of a large component, and all the small components contain at most 3 vertices.

Lemma 8. [28] Let $F$ be a vertices set of $A{Q}_n$ , $\left|F\right|\le 10n-74$ for $n\ge 8$ , $A{Q}_n-F$ is either connected, or it consists of a large component, and all the small components contain at most 4 vertices.

Lemma 9. [29] Let $P=\left(Y,X,Z\right)$ be a path of length two in $A{Q}_n$ between $Y$

and $Z$ for $n\ge 5$ . Then $\left|N_{A{Q}_n}\left(P\right)\right|\ge 6n-17$ and $\left|N_{A{Q}_n}\left(X\right)\cap N_{A{Q}_n}\left(Y\right)\cap N_{A{Q}_n}\left(Z\right)\right|\le 1$ . Furthermore, if $Z={\overline{X}}_n$ , we have $\left|N_{A{Q}_n}\left(P\right)\right|\ge 6n-15$ .

Lemma 10. [30] A graph $G$ has a perfect matching if and only if $o\left(G-X\right)\le \left|X\right|$ for all $X\subseteq V$ , where $o\left(G-X\right)$ is the number of connected components of $G-X$ with odd order.

3. Non-Inclusive 1-Good-Neighbor Diagnosability of $A{Q}_n$

3.1. Result under the PMC Model

In this section, we determine the non-inclusive $g$ -good-neighbor diagnosability of $A{Q}_n$ under the PMC model for $g=1$ .

Lemma 11. Let $A{Q}_n$ be an $n$ -dimensional augmented cube with $n\ge 9$ . Then $t_{N_1}\left(A{Q}_n\right)\le 8n-27$ .

Proof. Consider a 4-cycle $A=\left\{u,v,x,y\right\}$ in $A{Q}_n$ , where $v={\overline{u}}_2$ , $x={\overline{u}}_4$ , and $y={\overline{x}}_2$ (the notation ${\overline{u}}_i$ denotes the vertex obtained by flipping the $i$ -th bit of $u$ ). Let $D=N_{A{Q}_n}\left(A\right)$ ; define two fault sets $F_1=\left\{u,v\right\}\cup D$ and $F_2=\left\{x,y\right\}\cup D$ . By Lemma 5, $\left|D\right|=\left|N_{A{Q}_n}\left(\left\{u,v,x,y\right\}\right)\right|=8n-28$ for $n\ge 5$ . It is easy to verify that $F_1\Delta F_2=\left\{u,v,x,y\right\}$ , and neither $F_1\subseteq F_2$ nor $F_2\subseteq F_1$ , indicating that $F_1$ and $F_2$ are non-inclusive sets.

Since $uv\in E\left(A{Q}_n\right)$ and $v\notin F_2$ , we have $d_{A{Q}_n-F_2}\left(u\right)\ge 1$ and $d_{A{Q}_n-F_2}\left(v\right)\ge 1$ ; similarly, $xy\in E\left(A{Q}_n\right)$ implies $d_{A{Q}_n-F_1}\left(x\right)\ge 1$ and $d_{A{Q}_n-F_1}\left(y\right)\ge 1$ . Suppose there exists an isolated vertex $w\in V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ , then $N_{A{Q}_n}\left(w\right)\subseteq F_1\cap F_2$ . By Lemma 4, $\left|N_{A{Q}_n}\left(w\right)\cap N_{A{Q}_n}\left(z\right)\right|\le 4$ for any $z\in \left\{u,v,x,y\right\}$ . Since $A{Q}_n$ is $\left(2n-1\right)$ -regular, $\left|N_{A{Q}_n}\left(w\right)\right|=2n-1\ge 17$ when $n\ge 9$ , which implies that at least one neighbor of $w$ is not in $F_1\cap F_2$ . This contradiction shows that $\delta \left(A{Q}_n-F_1\right)\ge 1$ and $\delta \left(A{Q}_n-F_2\right)\ge 1$ , that is, each vertex in $A{Q}_n-F_1$ and $A{Q}_n-F_2$ has at least one good neighbors, so $F_1$ and $F_2$ are non-inclusive 1-good-neighbor fault sets.

According to the PMC model’s diagnosis rules, $F_1$ and $F_2$ are indistinguishable because there is no vertex $v\notin F_1\cup F_2$ that can distinguish them. Thus, $A{Q}_n$ is not non-inclusive 1-good-neighbor $\left(8n-26\right)$ -diagnosable, leading to $t_{N_1}\left(A{Q}_n\right)\le 8n-27$ .

Lemma 12. Let $A{Q}_n$ be an $n$ -dimensional augmented cube with $n\ge 23$ . Then $t_{N_1}\left(A{Q}_n\right)\ge 8n-27$ .

Proof. Assume for contradiction that there exist two distinct non-inclusive 1-good-neighbor fault sets $F_1$ and $F_2$ of $A{Q}_n$ with $\left|F_1\right|\le 8n-27$ and $\left|F_2\right|\le 8n-27$ , such that $F_1$ and $F_2$ are indistinguishable under the PMC model. First, we have $\left|F_1\cup F_2\right|\le \left|F_1\right|+\left|F_2\right|\le 16n-54<2^n$ for $n\ge 23$ , which implies that $V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ is non-empty.

Since $F_1$ and $F_2$ are 1-good-neighbor fault sets, $\delta \left(A{Q}_n-F_1\right)\ge 1$ and $\delta \left(A{Q}_n-F_2\right)\ge 1$ . For $n\ge 23$ , $\left|F_1\Delta F_2\right|\le 8n-29\le 10n-74$ , and $\left|V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\right)\right|\ge 2^n-\left(16n-54\right)>4$ for $n\ge 7$ . This indicates that $A{Q}_n-\left(F_1\cup F_2\right)$ contains a large connected component with at least 4 vertices.

Since $F_1$ and $F_2$ are indistinguishable, according to Proposition 1, all the vertices in $F_1\Delta F_2$ are not adjacent to each other in $A{Q}_n-\left(F_1\cup F_2\right)$ , which is $N_{A{Q}_n}\left(F_1\Delta F_2\right)\subseteq F_1\cap F_2$ . By Lemma 5, $\left|N_{A{Q}_n}\left(F_1\Delta F_2\right)\right|\ge 8n-28$ when $\left|F_1\Delta F_2\right|=4$ , which implies $\left|F_1\cap F_2\right|\ge 8n-28$ . However, $\begin{array}{c}\left|F_1\cap F_2\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cup F_2\right|\le \left(8n-27\right)+\left(8n-27\right)-\left(\left|F_1\Delta F_2\right|\right)\\ \le 16n-54-4=16n-58\end{array}$ , which contradicts $\left|F_1\cap F_2\right|\ge 8n-28$ for $n\ge 23$ . Thus, the lemma holds.

Theorem 13. For $n\ge 23$ , we have $t_{N_1}\left(A{Q}_n\right)=8n-27$ .

Proof. The conclusion follows directly from Lemmas 11 and 12.

3.2. Result under the MM^* Model

Lemma 14. For $n\ge 13$ , we have $t_{N_1}\left(A{Q}_n\right)\le 6n-17$ .

Proof. Consider a path $A=\left\{u,v,w\right\}$ of order 3 (with two edges) in $A{Q}_n$ , where $v={\overline{u}}_i$ and $w={\overline{u}}_j$ (here, ${\overline{u}}_k$ denotes the vertex formed by flipping the $k$ -th bit of $u$ ). Let $D=N_{A{Q}_n}\left(A\right)$ , and define two fault sets $F_1=\left\{u\right\}\cup D$ and $F_2=\left\{w\right\}\cup D$ . By Lemma 5, the size of $D$ (i.e., the neighborhood of path $A$ ) is $\left|D\right|=6n-17$ .

It is straightforward to verify that $F_1\Delta F_2=\left\{u,w\right\}$ , and neither $F_1$ is a subset of $F_2$ nor $F_2$ is contained in $F_1$ , which confirms that $F_1$ and $F_2$ form a pair of non-inclusive sets. Since $uv\in E\left(A{Q}_n\right)$ and $v\notin F_1\cup F_2$ , we have $d_{A{Q}_n-F_2}\left(u\right)\ge 1$ and $d_{A{Q}_n-F_2}\left(v\right)\ge 1$ ; similarly, $vw\in E\left(A{Q}_n\right)$ implies $d_{A{Q}_n-F_1}\left(v\right)\ge 1$ and $d_{A{Q}_n-F_1}\left(w\right)\ge 1$ .

By the construction of $F_1$ and $F_2$ , the neighborhood of the vertex set $V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\cup \left\{v\right\}\right)$ is entirely contained in $F_1\cap F_2$ . For $n\ge 13$ , $\left|D\right|=6n-17<8n-42$ , so Lemma 7 guarantees that $A{Q}_n-\left(F_1\cap F_2\right)$ remains connected. Additionally, the size of $V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\cup \left\{v\right\}\right)$ satisfies:

$\left|V\left(A{Q}_n\right)\right|-\left|F_1\cup F_2\right|-1\ge 2^n-\left(6n-15\right)-1=2^n-6n+14>3$

for $n\ge 13$ . This implies that $A{Q}_n-\left(F_1\cup F_2\cup \left\{v\right\}\right)$ contains a large connected component, and thus $\delta \left(A{Q}_n-\left(F_1\cup F_2\cup \left\{v\right\}\right)\right)\ge 1$ .

Under the MM^* model, $F_1$ and $F_2$ are indistinguishable because there is no vertex outside $F_1\cup F_2$ that can distinguish the two fault sets. Therefore, $A{Q}_n$ is not non-inclusive 1-good-neighbor $\left(6n-16\right)$ -diagnosable, leading to the conclusion that $t_{N_1}\left(A{Q}_n\right)\le 6n-17$ .

Lemma 15. For $n\ge 6$ , we have $t_{N_1}\left(A{Q}_n\right)\ge 6n-17$ .

Proof. Assume for contradiction that there exist two distinct non-inclusive 1-good-neighbor fault sets $F_1$ and $F_2$ of $A{Q}_n$ such that $\left|F_1\right|<6n-17$ , $\left|F_2\right|<6n-17$ , and $F_1$ and $F_2$ are indistinguishable under the MM^* model. Without loss of generality, suppose $F_1⊈F_2$ and $F_2⊈F_1$ .

According to Proposition 2, we can obtain the definition of the MM^* model’s indistinguishability, that is, for any vertex $w\in V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ , the neighborhood $N_{A{Q}_n}\left(w\right)$ cannot contain vertices from both $F_1\backslash F_2$ and $F_2\backslash F_1$ simultaneously. Let $W$ denote the set of vertices in $V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ whose neighborhoods intersect with $F_1\Delta F_2$ . For $A{Q}_n=A{Q}_{n-1}^0\oplus A{Q}_{n-1}^1$ (the recursive decomposition of augmented cubes), we have $N_{A{Q}_n}\left(w\right)\backslash F_1\subseteq F_2\backslash F_1$ or $N_{A{Q}_n}\left(w\right)\backslash F_2\subseteq F_1\backslash F_2$ for any $w\in W$ .

By the structural properties of $A{Q}_n$ , $\left|N_{A{Q}_n}\left(w\right)\cap \left(F_2\backslash F_1\right)\right|\le 6n-19$ and $\left|N_{A{Q}_n}\left(w\right)\cap \left(F_1\backslash F_2\right)\right|\le 6n-19$ . Since $A{Q}_n$ is $\left(2n-1\right)$ -regular, the size of $V\left(A{Q}_n\right)$ satisfies:

$2^n=\left|F_1\cup F_2\right|+\left|W\right|\le 2\left(6n-15\right)=12n-30$

However, for $n>6$ , $2^n>12n-30$ , which contradicts the above inequality. Furthermore, $\left|V\left(A{Q}_n\right)\backslash \left(F_1\cup F_2\cup W\right)\right|>2^n-12n+30>2$ for $n>6$ , implying the existence of a connected component $G_1$ in $A{Q}_n\backslash \left(F_1\cup F_2\right)$ with $\left|V\left(G_1\right)\right|\ge 3$ .

Since $F_1$ and $F_2$ are non-inclusive 1-good-neighbor fault sets, $\delta \left(A{Q}_n-F_1\right)\ge 1$ and $\delta \left(A{Q}_n-F_2\right)\ge 1$ . The contradiction arises from the fact that the structural constraints of $A{Q}_n$ force $F_1$ and $F_2$ to be distinguishable under the MM^* model. Thus, $t_{N_1}\left(A{Q}_n\right)\ge 6n-17$ .

Theorem 16. For $n\ge 13$ , we have $t_{N_1}\left(A{Q}_n\right)=6n-17$ under the MM^* model.

Proof. Combining the results of Lemmas 14 and 15, the non-inclusive 1-good-neighbor diagnosability of $A{Q}_n$ under the MM^* model is exactly $6n-17$ for $n\ge 13$ .

4. Discussion

The main results of this paper impose constraints on $n$ : $n\ge 23$ for the PMC model and $n\ge 13$ for the MM^* model. These constraints stem from two key aspects of the proof process: 1) The induction step relies on the minimum size of subgraph components in $A{Q}_n$ . For smaller $n$ , the subgraphs may not retain the required connectivity and expansion properties, leading to the failure of key inequalities in the proof. 2) The verification of 1-good-neighbor condition requires sufficient neighbors for each fault-free vertex. For $n<13$ , the number of neighbors $\left(2n-1\right)$ is insufficient to guarantee at least one fault-free neighbor when facing the upper bound of fault sets.

Regarding the tightness of these constraints, we conjecture that they can be partially tightened. For example, preliminary analysis shows that the constraint for the MM^* model may be reduced to $n\ge 10$ by optimizing the component size estimation in the proof. However, further verification requires refining the induction base and adjusting the fault set partitioning strategy, which will be the focus of future work.

Extending the current analysis to $g$ -good-neighbor diagnosability with $g\ge 2$ faces three core challenges: 1) Fault set structure complexity: For $g=2$ , each fault-free vertex must have at least two fault-free neighbors, which requires stricter control over the distribution of fault sets. Unlike $g=1$ , the fault sets can no longer be concentrated in local regions, increasing the difficulty of partitioning and analysis. 2) Component connectivity requirements: The proof for $g=1$ leverages the 1-extra connectivity of $A{Q}_n$ , but for $g\ge 2$ , higher-order extra connectivity parameters (e.g., 2-extra connectivity) are needed and integrating this into diagnosability analysis requires new technical tools. 3. Model-specific constraints: Under the MM^* model, the distinguishability conditions for $g\ge 2$ involve more complex test outcome combinations. The mutual testing between fault-free and faulty vertices requires more detailed case analysis, especially for non-adjacent fault-free vertices.

5. Conclusions

This study focuses on the non-inclusive 1-good-neighbor diagnosability of augmented cubes $A{Q}_n$ , a class of interconnection networks with excellent topological properties. Through systematic analysis of the structural characteristics of $A{Q}_n$ and rigorous mathematical proof, we derive the exact values of the non-inclusive 1-good-neighbor diagnosability under two classic fault diagnosis models: 1) Under the PMC model, $t_{N_1}\left(A{Q}_n\right)=8n-27$ for $n\ge 23$ ; 2) Under the MM^* model, $t_{N_1}\left(A{Q}_n\right)=6n-17$ for $n\ge 13$ .

These findings quantify the fault tolerance capability of augmented cubes in the context of non-inclusive fault sets and 1-good-neighbor constraints, providing valuable theoretical support for the design and optimization of reliable multiprocessor systems. The proof methods adopted in this study, including structural construction, proof by contradiction, and induction, can be extended to the analysis of other interconnection network topologies.

Future research directions may include extending the results to $g\ge 2$ (i.e., non-inclusive $g$ -good-neighbor diagnosability) and investigating the non-inclusive diagnosability of other network structures such as folded hypercubes, alternating group graphs, and $\left(n,k\right)$ -star networks. Additionally, exploring the non-inclusive diagnosability under more realistic fault models (e.g., intermittent fault models) could further advance the research on network reliability.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 16, 848-854.[CrossRef]
[2]	Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceedings of 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 31-36.
[3]	Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396.[CrossRef]
[4]	Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175.[CrossRef]
[5]	Wang, D. (1999) Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 48, 1369-1374.[CrossRef]
[6]	Chang, G.-Y., Chang, G.J. and Chen, G.-H. (2005) Diagnosabilities of Regular Networks. IEEE Transactions on Parallel and Distributed Systems, 16, 314-323.[CrossRef]
[7]	Li, X., Fan, J., Lin, C. and Jia, X. (2017) Diagnosability Evaluation of the Data Center Network Dcell. The Computer Journal, 61, 129-143.[CrossRef]
[8]	Chen, M., Habib, M. and Lin, C. (2022) Diagnosability for a Family of Matching Composition Networks. The Journal of Supercomputing, 79, 7584-7608.[CrossRef]
[9]	Chen, B. and Li, F. (2024) Diagnosability of the Lexicographic Product of Cycles and Paths under PMC Model. 2024 7th International Conference on Information and Computer Technologies (ICICT), Honolulu, 15-17 March 2024, 301-308.[CrossRef]
[10]	Peng, S.L., Lin, C.K., Tan, J.J. and Hsu, L.H. (2012) The G-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412.[CrossRef]
[11]	Hsieh, S. and Kao, C. (2012). The Conditional Diagnosability of K-Ary N-Cubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 62, 839-843. [Google Scholar] [CrossRef]
[12]	Li, D. and Lu, M. (2017) The G-Good-Neighbor Conditional Diagnosability of Star Graphs under the PMC and MM* Model. Theoretical Computer Science, 674, 53-59.[CrossRef]
[13]	Liu, H.Q., Hu, X.L. and Gao, S. (2019) The g-Good-Neighbor Conditional Diagnosability of Locally Exchanged Twisted Cubes. The Computer Journal, 63, 89-90.[CrossRef]
[14]	Ding, T., Xu, M. and Zhu, Q. (2020) The Non-Inclusive Diagnosability of Hypercubes under the MM* Model. International Journal of Foundations of Computer Science, 31, 929-940.[CrossRef]
[15]	Ma, M., Xu, M., Ding, T., Li, X. and Zhu, Q. (2022) The Non-Inclusion Diagnosability of Hypercubes under the PMC Model. Journal of the Operations Research Society of China, 12, 478-484.[CrossRef]
[16]	Zhuo, N., Zhang, S., Chang, J. and Ye, C. (2025) Non-Inclusive Diagnosability of Folded Hypercube-Like Networks. Discrete Applied Mathematics, 364, 237-246.[CrossRef]
[17]	Zhuo, N., Zhang, S., Ye, C. and Li, Y. (2023) Non-Inclusive Diagnosability of Alternating Group Graphs. Parallel Processing Letters, 33, Article ID: 2350007.[CrossRef]
[18]	Chen, Q., Liu, J., Lee, C., Wu, J. and Li, G. (2025) The Reliability of (n,k)-Star Network in Terms of Non-Inclusive Fault Pattern. Theoretical Computer Science, 1039, Article ID: 115189.[CrossRef]
[19]	Yuan, J., Li, Y., Liu, A. and Qiao, H. (2022) The Non-Inclusive G-Good-Neighbor Diagnosability of Interconnection Networks. Theoretical Computer Science, 922, 179-192.[CrossRef]
[20]	Zhang, S., Tian, T., Li, Y. and Ye, C. (2024) Non-Inclusive g-Good-Neighbour Diagnosability of Hypercubes. International Journal of Computer Mathematics: Computer Systems Theory, 9, 54-63.[CrossRef]
[21]	Dahbura and Masson (1984) An 0(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492.[CrossRef]
[22]	Kan, S., Fan, J., Cheng, B., Wang, X. and Zhou, J. (2021) Structure Fault-Tolerance of the Augmented Cube. Journal of Internet Technology, 21, 1733-1746.
[23]	Zhang, H., Xu, X., Wang, Z., Zhang, Q. and Yang, Y. (2021) (2n-3)-Fault-Tolerant Hamiltonian Connectivity of Augmented Cubes AQn. AIMS Mathematics, 6, 3486-3511.[CrossRef]
[24]	Zhang, Q., Xu, L. and Yang, W. (2021) Reliability Analysis of the Augmented Cubes in Terms of the Extra Edge-Connectivity and the Component Edge-Connectivity. Journal of Parallel and Distributed Computing, 147, 124-131.[CrossRef]
[25]	Hong, W. and Hsieh, S. (2011) Strong Diagnosability and Conditional Diagnosability of Augmented Cubes under the Comparison Diagnosis Model. IEEE Transactions on Reliability, 61, 140-148.[CrossRef]
[26]	Ma, M., Liu, G. and Xu, J. (2008) The Super Connectivity of Augmented Cubes. Information Processing Letters, 106, 59-63.[CrossRef]
[27]	Chang, N.-W. and Hsieh, S.-Y. (2012) Conditional Diagnosability of Augmented Cubes under the PMC Model. IEEE Transactions on Dependable and Secure Computing, 9, 46-60.[CrossRef]
[28]	Cheng, E., Lipták, L., Qiu, K., Shen, Z. and Vangipuram, A. (2023) On the G-Extra Connectivity of Augmented Cubes. Theoretical Computer Science, 970, Article ID: 114059.[CrossRef]
[29]	Ma, M., Song, Y., Xu, J. and Haynes, T.W. (2013) Fault Tolerance of Augmented Cubes. AKCE International Journal of Graphs and Combinatorics, 10, 37-55.[CrossRef]
[30]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer.