Minimum Neighborhood of Alternating Group Graphs

• Published in: IEEE access 2019, Vol.7, p.17299-17311
• Main Authors: Huang, Yanze, Lin, Limei, Wang, Dajin, Xu, Li
• Format: Article
• Language: English
• Subjects: alternating group graphs; Apexes; Artificial neural networks; Combinatorial analysis; combinatorial property; Fault tolerance; Fault tolerant systems; Graph theory; independent set; Informatics; Mathematics; Minimum neighborhood; Multiprocessing; Multiprocessing systems; Multiprocessor interconnection; Neighborhoods
• ISSN: 2169-3536; 2169-3536
• DOI: 10.1109/ACCESS.2019.2896101

The minimum neighborhood and combinatorial property are two important indicators of fault tolerance of a multiprocessor system. Given a graph G , \theta _{G}(q) is the minimum number of vertices adjacent to a set of q vertices of G ( 1\leq q\leq |V(G)| ). It is meant to determine \theta _{G}(q) , the minimum neighborhood problem (MNP). In this paper, we obtain \theta _{AG_{n}}(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 \theta _{AG_{n}}(2)=4n-10 . Next, we prove that \theta _{AG_{n}}(3)=6n-16 . Finally, we propose that \theta _{AG_{n}}(4)=8n-24 .