Fault tolerance analysis for hamming graphs with large-scale faulty links based on k-component edge-connectivity.

The L -ary n -dimensional hamming graph K L n is one of the most attractive interconnection networks for parallel processing and computing systems. Analysis of the link fault tolerance of topology structure can provide the theoretical basis for the design and optimization of the interconnection networks. The k -component edge-connectivity c λ k (G) of an interconnection network G , is the minimum number of set of faulty links, such that these malfunctions disconnect the network G with at least k connected subnetworks. It gives a more precise quantitative analysis of indicators of the robustness of a parallel distributed system in the event of faulty links. Let t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. In this paper, we prove that the (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs is c λ k + 1 (K L n) = (L − 1) n k − e x k (K L n) 2 for k ≤ L t , n ≥ 7 , where e x k (K L n) represents the maximum degree sum of the subgraph induced by all k processors of K L n. As the exact values of (k + 1) -component edge-connectivity of K L n oscillate greatly, an efficient O (log ⁡ N) algorithm is designed to determine the exact values of c λ k + 1 (K L n) for each k ≤ L t and N = L n. Our result improves those of Xu et al. [33] and Liu et al. [27]. • The (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs K L n is explored. • Determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and n ≥ 7 , where t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. • An efficient O (l o g N) algorithm is designed to determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and N = L n. [ABSTRACT FROM AUTHOR]