Fault tolerance assessment for hamming graphs based on r-restricted R-structure(substructure) fault pattern

The interconnection network between the storage system and the multi-core computing system is the bridge for communication of enormous amounts of data access and storage, which is the critical factor in affecting the performance of high-performance computing systems. By enforcing additional restrictions on the definition of R-structure and R-substructure connectivities to satisfy that each remaining vertex has not less than r neighbors, we can dynamically assess the cardinality of the separated component to meet the above conditions under structure faulty, thereby enhancing the evaluation of the fault tolerance and reliability of high-performance computing systems. Let R be a connected subgraph of a connected graph G. The r-restricted R-structure connectivity κr(G;R) (resp. r-restricted R-substructure connectivity κrs(G;R)) of G is the minimum cardinality of a set of subgraphs F={F1,F2,…,Fm} such that Fi is isomorphic to R (resp. Fi is a connected subgraph of R) for 1≤i≤m, and G−F is disconnected with the minimum degree of each component being at least r. Note that κr(G;K1) reduces to r-restricted connectivity κr(G) (also called r-good neighbor connectivity). In this paper, we focus on κr(KLn;R) and κrs(KLn;R) for the L-ary n-dimensional hamming graph KLn, where R∈{K1,K1,1,KL1}. For 0≤r≤n−3, n≥3 and L≥3, we determine the (L−1)r-good neighbor connectivity of KLn, i.e., κ(L−1)r(KLn)=(L−1)(n−r)Lr, and the (L−1)r-good neighbor diagnosability of KLn under the PMC model and MM* model, i.e., t(L−1)r(KLn)=[(L−1)(n−r)−1]Lr−1. And we also drive that κ(L−1)r(KLn;K1,1)=κ(L−1)rs(KLn;K1,1)=12(L−1)Lr(n−r) for 1≤r≤n−3, n≥4. Moreover, we offer an upper bound of κ2(KLn;KL1) (resp. κ2s(KLn;KL1)) for n≥3, and establish that it is sharp for ternary n-cubes K3n. Specifically, κ2(K3n;K31)=κ2s(K3n;K31)=2(n−1) for n≥3.