# IFDA: Intermittent Fault Diagnosis Algorithm for Augmented Cubes Under the PMC Model
## 3 Properties of Augmented Cubes  
Recursion is defined as follows: \begin{table}
\begin{tabular}{c c c} \hline \(u\rightarrow v\) & \(v\rightarrow u\) & **Interpretation** \\ \hline
0 & 0 & \(u\), \(v\) in same property \\
1 & 0 & contains intermittent fault in \(u\) and \(v\) \\
1 & 1 & contains intermittent fault in \(u\) and \(v\) \\ \hline \end{tabular}
\end{table} 
Table 2: Diagnosis result interpretation under the PMC model. An \(n\)-dimensional augmented cube is denoted \(AQ_{n}\). \(AQ_{1}\) is a complete graph \(K_{2}\), whose two vertices are marked with \(0\) and \(1\), respectively. When \(n\geq 2\), \(AQ_{n}\) can be obtained by adding \(2^{n}\) edges between two \((n-1)\)-dimensional augmented cubes labeled \(AQ_{n-1}^{0}\) and \(AQ_{n-1}^{1}\), respectively, where \(V\big{(}AQ_{n-1}^{0}\big{)}=\{0a_{n-1}\ldots a_{2}a_{1}:a_{i}\in\{0,1\}\}\), and \(V\big{(}AQ_{n-1}^{1}\big{)}=\{1b_{n-1}\ldots b_{2}b_{1}:b_{i}\in\{0,1\}\}\). A node \(u=0a_{n-1}\ldots a_{2}a_{1}\) of \(AQ_{n-1}^{0}\) is adjacent to a node \(v=1b_{n-1}\ldots b_{2}b_{1}\) of \(AQ_{n-1}^{1}\) if and only if either (1) \(a_{i}=b_{i}\) for \(1\leq i\leq(n-1)\), in which case \((u,v)\) is called a hypercube edge, or (2) \(a_{i}=\tilde{b_{i}}\) for \(1\leq i\leq(n-1)\), in which case \((u,v)\) is called a complement edge. Figure 1 shows \(AQ_{1}\), \(AQ_{2}\), and \(AQ_{3}\). The number of nodes in an n-dimensional augmented cube is given by \(2^{n}\), which directly follows from its definition (e.g., \(AQ_{5}\) contains 32 nodes, \(AQ_{6}\) contains 64 nodes, etc.). According to the above definition, it is recorded as \(AQ_{n}=AQ_{n-1}^{0}\oplus AQ_{n-1}^{1}\). We use \(L\) for \(AQ_{n-1}^{0}\) and \(R\) for \(AQ_{n-1}^{1}\). That is, \(AQ_{n}=L\oplus R\). We call the edge between \(L\) and \(R\) the cross edge, and we call \(L\) and \(R\) the subcube. Obviously each vertex in \(AQ_{n}\) has two cross edges, i.e., a vertex in \(L\) has two vertices in \(R\) and vice versa. Sometimes we also use \(0X_{n-1}X_{n-2}\ldots X_{1}\) and \(1X_{n-1}X_{n-2}\ldots X_{1}\) to represent \(AQ_{n-1}^{0}\) and \(AQ_{n-1}^{1}\), where \(X_{i}\in\{0,1\}\). Obviously, \(AQ_{n}\) is \((2n-1)\)-regular. For any \(n\)-bit binary string \(u=a_{n}a_{n-1}\ldots a_{1}\). We use \(u_{i}\) to denote the binary string \(a_{n}\ldots a_{i+1}\tilde{a_{i}}a_{i-1}\ldots a_{1}\) and \(\tilde{u_{i}}\) to denote the binary string \(a_{n}\ldots a_{i+1}\tilde{a_{i}}\tilde{a_{i-1}}\ldots\tilde{a_{1}}\). Above, we give a recursive definition of an \(n\)-dimensional augmented cube; however, according to the recursive definition it is not a good representation of the structural characteristics of an augmented cube. Below, we give a nonrecursive definition of an \(n\)-dimensional augmented cube. Definition 2: The set of points of \(AQ_{n}\) is an array of \(n\)-elements defined on the set \(\{0,1\}\), i.e., \(V(AQ_{n})=\{a_{n}a_{n-1}\ldots a_{1}:a_{i}\in\{0,1\}\}\). There are edges between the two vertices of \(AQ_{n}\), \(u=a_{n}a_{n-1}\ldots a_{1}\) and \(v=b_{n}b_{n-1}\ldots b_{1}\), if and only if there is a positive integer \(i\in[1,n]\), \(v=u_{i}\), or, there is a positive integer \(i\in[2,n]\), \(v=\tilde{u_{i}}\). Property 1 ([15]): \(\kappa(AQ_{1})=1,\kappa(AQ_{2})=3,\kappa(AQ_{3})=4\), and \(\kappa(AQ_{n})=2n-1\) for \(n\geq 4\). **Property 2** ([27]). : _Let \(AQ_{n}=L\oplus R\), where \(L\cong AQ_{n-1}^{0}\) and \(R\cong AQ_{n-1}^{1}\), and \(u\) and \(v\) are two nodes in \(L\). Then, \((u,v)\) is a complement pair of \(L(i.e.,v=\bar{u}_{n-1})\) if and only if they have common (more precisely, exactly two) neighbors in \(R\). Moreover, if \((u,v)\) is not a complement pair of \(L\), then \(u\) and \(v\) have no common neighbor._  
**Lemma 4** ([28]). : _Let \(x\) and \(y\) be two arbitrary nodes in \(AQ_{n}\), where \(n\geq 2\). Then, \(\left|N_{AQ_{n}}(\{x,y\})\right|\geq 4n-8\) holds._  
**Lemma 5** ([28]). : _Let \(x,y,z\) be three nodes in \(AQ_{n}\), where \(n\geq 3\). Then, \(\left|N_{AQ_{n}}(\{x,y,z\})\right|\geq 6n-17\) holds._  
**Lemma 6** ([28]).