The structure fault tolerance of arrangement graphs

Guozhen Zhang, Dajin Wang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The arrangement graph An,k is a prominent underlying topology for multi-processor/multi-computer networks. In this paper, we study the structure fault tolerance of An,k for two structures of interest and significance - the m-leaves star Sm, and the m-leaves 2-step star T2m. 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={H1,H2,…,Ht}, such that for each and every 1≤i≤t, Hi⊆G and Hi 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 κ(An,k;H) and κs(An,k;H) for H∈{Sm,T2m}. Our result adds to the many known, desirable properties of An,k, providing more perspectives when considering its candidacy as an interconnection network for multiprocessor systems.

Original languageEnglish
Article number126039
JournalApplied Mathematics and Computation
StatePublished - 1 Jul 2021


  • 2-step stars
  • Arrangement graphs
  • Interconnection networks
  • Stars
  • Structure connectivity
  • Substructure connectivity


Dive into the research topics of 'The structure fault tolerance of arrangement graphs'. Together they form a unique fingerprint.

Cite this