The Component Connectivity of Alternating Group Graphs and Split-Stars

Abstract

For an integer $\ell ⩾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 $A{G}_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(A{G}_n)=4n-10$ and ${\kappa }_4(A{G}_n)=6n-16$ for $n⩾4$, and ${\kappa }_5(A{G}_n)=8n-24$ for $n⩾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 $n⩾4$.

References in corpus (3)

• The 4-Component Connectivity of Alternating Group Networks
• Reliability evaluation of folded hypercubes in terms of component connectivity
• Two kinds of generalized connectivity of dual cubes