Structure Connectivity and Substructure Connectivity of Alternating Group Graphs

摘要

The alternating group graph, denoted by AG_n, is one of the popular interconnection networks. In this paper, we consider two network connectivities, H-structure-connectivity and H-substructure-connectivity, which are new measures for a network's reliability and fault-tolerability. We say that a set F of connected subgraphs of G is a subgraph-cut of G if G-V (F) is a disconnected or trivial graph. Let H be a connected subgraph of G. Then F is an H-structure-cut, if F is a subgraph-cut, and every element in F is isomorphic to H. And F is an H-substructure-cut if F is a subgraph-cut, such that every element in F is isomorphic to a connected subgraph of H. The H-structure-connectivity(resp. H-substructure-connectivity) of G, denoted by κ(G;H)(resp. κ^{s(G;H)), is the minimum cardinality of all H-structure-cuts(resp. H-substructure-cuts) of G. In this paper, we will establish both κ(AG_n;H) and κ(AG_n;H) for the alternating group graph AG_n and H ∈{K₁,K_1,1,K_1,2}.}