Structure Fault Tolerance of Recursive Interconnection Networks. (30th January 2020) - Sabir, Eminjan; Meng, Jixiang
Abstract: Motivated by effects caused by structure link faults in networks, we study the following graph theoretical problem. Let T be a connected subgraph of a graph G except for K_1 . The T -structure edge-connectivity λ (G;T) (resp. T -substructure edge-connectivity λ ^s(G;T) ) of G is the minimum cardinality of a set of edge-disjoint subgraphs F={T_1, T_2, …, T_m} (resp. F={T_1^^′, T_2^^′, …, T_m^^′} ) such that T_i is isomorphic to T (resp. T_i^^′ is a connected subgraph of T ) for every 1 i m, and E(F) 's removal leaves the remaining graph disconnected. In this paper, we determine both λ (G;T) and λ ^s(G;T) for (1) the hypercube Q_n and T{K_1, 1, K_1, 2, K_1, 3, P_4, Q_1, Q_2, Q_3} ; (2) the k -ary n -cube Q^k_n (k3) and T{K_1, 1, K_1, 2, K_1, 3, Q^3_1, Q^4_1} ; (3) the balanced hypercube BH_n and T{K_1, 1, K_1, 2, BH_1} . We also extend some known results.