The 4-Component Connectivity of Alternating Group Networks
share
The ℓ-component connectivity (or ℓ-connectivity for short) of a graph G, denoted by κ_ℓ(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least ℓ components or a graph with fewer than ℓ vertices. This generalization is a natural extension of the classical connectivity defined in term of minimum vertex-cut. As an application, the ℓ-connectivity can be used to assess the vulnerability of a graph corresponding to the underlying topology of an interconnection network, and thus is an important issue for reliability and fault tolerance of the network. So far, only a little knowledge of results have been known on ℓ-connectivity for particular classes of graphs and small ℓ's. In a previous work, we studied the ℓ-connectivity on n-dimensional alternating group networks AN_n and obtained the result κ_3(AN_n)=2n-3 for n≥ 4. In this sequel, we continue the work and show that κ_4(AN_n)=3n-6 for n≥ 4.
READ FULL TEXT