Minimum Neighborhood of Alternating Group Graphs

Abstract

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 ≤ q ≤ |V(G)|). It is meant to determine θG(q), the minimum neighborhood problem (MNP). In this paper, we obtain θAG0(q) for an independent set with size q in an n-dimensional alternating group graph AGn, a well-known interconnection network for multiprocessor systems. We first propose some combinatorial properties of AGn. 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.

Keywords

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