## 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 ≤|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 language | English |
---|---|

Article number | 8629905 |

Pages (from-to) | 17299-17311 |

Number of pages | 13 |

Journal | IEEE Access |

Volume | 7 |

DOIs | |

State | Published - 1 Jan 2019 |

## Keywords

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