Minimum Neighborhood of Alternating Group Graphs

Yanze Huang, Limei Lin, Dajin Wang, Li Xu

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Article number8629905
Pages (from-to)17299-17311
Number of pages13
JournalIEEE Access
Volume7
DOIs
StatePublished - 1 Jan 2019

Fingerprint

Fault tolerance

Keywords

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

Cite this

Huang, Yanze ; Lin, Limei ; Wang, Dajin ; Xu, Li. / Minimum Neighborhood of Alternating Group Graphs. In: IEEE Access. 2019 ; Vol. 7. pp. 17299-17311.
@article{26d94bf98166411a9efa899009720146,
title = "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 ≤|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.",
keywords = "Minimum neighborhood, alternating group graphs, combinatorial property, fault tolerance, independent set",
author = "Yanze Huang and Limei Lin and Dajin Wang and Li Xu",
year = "2019",
month = "1",
day = "1",
doi = "10.1109/ACCESS.2019.2896101",
language = "English",
volume = "7",
pages = "17299--17311",
journal = "IEEE Access",
issn = "2169-3536",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Minimum Neighborhood of Alternating Group Graphs. / Huang, Yanze; Lin, Limei; Wang, Dajin; Xu, Li.

In: IEEE Access, Vol. 7, 8629905, 01.01.2019, p. 17299-17311.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Minimum Neighborhood of Alternating Group Graphs

AU - Huang, Yanze

AU - Lin, Limei

AU - Wang, Dajin

AU - Xu, Li

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Minimum neighborhood

KW - alternating group graphs

KW - combinatorial property

KW - fault tolerance

KW - independent set

UR - http://www.scopus.com/inward/record.url?scp=85061699184&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2896101

DO - 10.1109/ACCESS.2019.2896101

M3 - Article

VL - 7

SP - 17299

EP - 17311

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

M1 - 8629905

ER -