For an integer $ellgeqslant 2$, the $ell$-component connectivity 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 is a natural generalization of the classical connectivity of graphs defined in term of the minimum vertex-cut and is a good measure of robustness for the graph corresponding to a network. So far, the exact values of $ell$-connectivity are known only for a few classes of networks and small $ell$s. It has been pointed out in~[Component connectivity of the hypercubes, Int. J. Comput. Math. 89 (2012) 137--145] that determining $ell$-connectivity is still unsolved for most interconnection networks, such as alternating group graphs and star graphs. In this paper, by exploring the combinatorial properties and fault-tolerance of the alternating group graphs $AG_n$ and a variation of the star graphs called split-stars $S_n^2$, we study their $ell$-component connectivities. We obtain the following results: (i) $kappa_3(AG_n)=4n-10$ and $kappa_4(AG_n)=6n-16$ for $ngeqslant 4$, and $kappa_5(AG_n)=8n-24$ for $ngeqslant 5$; (ii) $kappa_3(S_n^2)=4n-8$, $kappa_4(S_n^2)=6n-14$, and $kappa_5(S_n^2)=8n-20$ for $ngeqslant 4$.
Download