The structure fault tolerance of arrangement graphs

The arrangement graph A_n,k is a prominent underlying topology for multi-processor/multi-computer networks. In this paper, we study the structure fault tolerance of A_n,k for two structures of interest and significance - the m-leaves star S_m, and the m-leaves 2-step star T_2m. Let G be a connected graph and H a connected subgraph of G. The H-structure connectivity κ(G;H) (resp. H-substructure connectivity κ^s(G;H)) of G is the cardinality of a minimum collection F={H₁,H₂,…,H_t}, such that for each and every 1≤i≤t, H_i⊆G and H_i is isomorphic to H (resp. isomorphic to a connected subgraph of H), and the removal of F disconnects G. In this paper, we will determine κ(A_n,k;H) and κ^s(A_n,k;H) for H∈{S_m,T_2m}. Our result adds to the many known, desirable properties of A_n,k, providing more perspectives when considering its candidacy as an interconnection network for multiprocessor systems.