부산대학교 도서관

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 1 ,K 1,1 ,K 1,2 }.