Minimum Neighborhood of Alternating Group Graphs

Yanze Huang, Limei Lin, Dajin Wang, Li Xu

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


The minimum neighborhood and combinatorial property are two important indicators of fault tolerance of a multiprocessor system. Given a graph G , θ G (q) is the minimum number of vertices adjacent to a set of q vertices of G (1 ≤|V(G)| ). It is meant to determine θ G (q), the minimum neighborhood problem (MNP). In this paper, we obtain θ AGn (q) for an independent set with size q in an n -dimensional alternating group graph AG n , a well-known interconnection network for multiprocessor systems. We first propose some combinatorial properties of AG n . Then, we study the MNP for an independent set of two vertices and obtain that θ AGn (2)=4n-10. Next, we prove that θ AGn (3)=6n-16. Finally, we propose that θ AGn (4)=8n-24.

Original languageEnglish
Article number8629905
Pages (from-to)17299-17311
Number of pages13
JournalIEEE Access
StatePublished - 2019


  • Minimum neighborhood
  • alternating group graphs
  • combinatorial property
  • fault tolerance
  • independent set


Dive into the research topics of 'Minimum Neighborhood of Alternating Group Graphs'. Together they form a unique fingerprint.

Cite this