The 4-Component Connectivity of Alternating Group Networks

Abstract

The $\ell$-component connectivity (or $\ell$-connectivity for short) of a graph $G$, denoted by ${\kappa }_{\ell }(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $\ell$ components or a graph with fewer than $\ell$ vertices. This generalization is a natural extension of the classical connectivity defined in term of minimum vertex-cut. As an application, the $\ell$-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 $\ell$-connectivity for particular classes of graphs and small $\ell$'s. In a previous work, we studied the $\ell$-connectivity on $n$-dimensional alternating group networks $A{N}_n$ and obtained the result ${\kappa }_3(A{N}_n)=2n-3$ for $n⩾4$. In this sequel, we continue the work and show that ${\kappa }_4(A{N}_n)=3n-6$ for $n⩾4$.