## 5 The t/k-Diagnosability of the BCCC Network under the MM\({}^{*}\) Model  
In this section, we will calculate the t/k-diagnosability of \(BC_{n,k}\) under the MM\({}^{*}\) model for \(1\leq k\leq n-1\). In the t/k diagnosis strategy, we represent the number of misdiagnosed nodes with \(k\). Meanwhile, in BCCC(n,k), different dimensions are represented with \(k\). Hence, in order to differentiate them, we replace \(k\) with \(h\) to represent the number of misdiagnosed nodes in the t/k diagnosis. Definition 3 ([27]): Given a graph \(G=(V(G),E(G))\) and a syndrome \(\sigma\) on \(G\) produced by a faulty set, let \(x\subseteq V(G)\); the \(0\)-test subset of node \(x\) is denoted as \(C_{0}(x)=\{c\in V(G)|\exists a\in V(G)\), \(\sigma(x,a)_{c}=0\}\). The \(0\)-test subgraph of \(G\), denoted \(T_{0}(G)\), is a subgraph of \(G\) defined by \(V(T_{0}(G))\subseteq V(G)\) and \(E(T_{0}(G))=\{(x,c)\in E(G)|c\in C_{0}(x),x\in C_{0}(c)\}\). Figure 4: Illustration of \(F_{1}\cap F_{2}\) is a g-extra vertex cut. **Lemma 12**. : _Assume a system \(G=(V(G),E(G))\) includes at most \(t\) failure nodes and symptom \(\sigma\) caused by failure sets in \(G\). We come up with the following conclusions:_  
1. _If for any node_ \(x\)_, there are_ \(y\in V(G)\) _and_ \((x,y)\in E(G)\) _that makes_ \(x\in C_{0}(y)\) _and_ \(y\in C_{0}(x)\)_, then_ \(x\) _and_ \(y\) _share the same state (fault or fault-free)._
2. _For any random connected component_ \(R\in T_{0}(G)\)_, all nodes_
3. _If in_ \(T_{0}(G)\) _the connected component_ \(R\) _meets condition_ \(|V(R)|\geq t+1\)_, then all the nodes in_ \(R\) _are fault-free._  
Proof. : (1) Given a proof by contradiction, suppose that node \(x\) is faulty and \(y\) is fault-free. Select a node \(z\in N_{G}(x)\) and \(z\
eq y\), then \(\sigma(y,z)_{x}\
eq 0\). Based on the MM* model, we have \(y\
otin C_{0}(x)\); then, there is a contradiction. 2. When \(|V(R)|=1\), the result clearly holds. Next, we consider the situation of \(|V(R)|\geq 2\). Let \(x\in V(R)\) and for any \(y\in N_{R}(x)\). It can be obtained that \(y\in C_{0}(x)\) and \(x\in C_{0}(y)\). According to Conclusion 1 of this Lemma, \(x\) and \(y\) share the same state. In other words, in \(N_{R}(x)\), all the nodes share the same state as \(x\). Similarly, all nodes in \(R\) share the same state. That is to say, all nodes in R are faulty, or all nodes in R are fault-free. 3. Since system \(G\) contains at most \(t\) fault nodes, it follows from the conclusion 2 of this Lemma that all nodes in \(R\) have the same state. Assuming that all nodes in \(R\) are faulty, then \(|V(R)|\leq t\), there is a contradiction. Then, all nodes in \(R\) are fault-free. **Theorem 3**. : _For any integers \(n\geq 3\), \(k\geq 2\), \(n\geq k+1\) and \(1\leq h\leq n-1\), \(BC_{n,k}\) is \([(h+1)(k-1)+n]/h\)-diagnosable under the MM* model._  
Proof. : Case 1: \(|F|\leq(h+1)(k-1)+n-1\). According to Lemma 7, \(BC_{n,k}-F\) has one large component \(S\) and \(|V(S)|\geq N-|F|-h\). Meanwhile, \(|V(S)|=mc(BC_{n,k}-F)=mc(T_{0}^{\prime}(BC_{n,k}))\). Thus, we have  
\[|V(S)| =mc(BC_{n,k}-F) \tag{8}\] \[\geq N-|F|-h\] \[\geq N-[(h+1)(k-1)+n-1]-h\] \[\geq(k+1)n^{k+1}-[(h+1)(k-1)+n-1]-h\] \[\geq(k+1)n^{k+1}-n(k+1)+2\] \[>|F|\]  
According to Lemma 12, all nodes in S are fault free where \(|V(S)|\geq|F|\). Then,  
\[|F^{\prime}| =N-|V(S)| \tag{9}\] \[\leq N-(N-|F|-h)\] \[=|F|+h\]  
\(F^{\prime}\) contains at most \(h\) fault-free nodes. Case 2: \(|F|=(h+1)(k-1)+n\). Let H be a set of suspicious nodes and \(H\subseteq F^{\prime}\). Therefore, \(N_{BC_{n,k}}(H)\subseteq F\). If \(|H|\leq h\), \(|F^{\prime}|=|F|+h\), the theorem holds. Then, we consider that \(|H|\geq h+1\). If \(|H|\geq h+1\), we need to prove \(|N_{BC_{n,k}}(H)|\geq t\). Suppose that \(|N_{BC_{n,k}}(H)|\leq t-1\). According to Lemma 6, the remaining small components C have the most \(h\) vertices in total and \(|H|\leq h\). This is in contradiction to \(|H|\geq h+1\). By Lemma 5, \(N_{BC_{n,k}}(H)\geq(h+1)(k-1)+n\) and \(H\cap F=\emptyset\).