Summary: The \(\ell\)-component connectivity of a graph \(G\), denoted by \(c\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 terms of the minimum vertex-cut. Since this parameter can be used to evaluate the reliability and fault tolerance of a graph \(G\) corresponding to a network, determining the exact values of \(c\kappa_\ell(G)\) is an important issue on the research topic of networks. However, it has been pointed out in [L.-H. Hsu et al., Int. J. Comput. Math. 89, No. 2, 137–145 (2012; Zbl 1238.05218)] that determining \(\ell\)-component connectivity is still unsolved in most interconnection networks even for small \(\ell\)’s. Let \(BS_n\) and \(BP_n\) denote the \(n\)-dimensional bubble-sort star graph and the \(n\)-dimensional burnt pancake graph, respectively.
In this paper, for \(BS_n\), we determine the values: \(c\kappa_3(BS_n)=4n-9\) for \(n\geqslant 3\), and \(c\kappa_4(BS_n)=6n-16\) and \(c\kappa_5(BS_n)=8n-24\) for \(n\geqslant 4\). Similarly, for \(BP_n\), we determine the values: \(c\kappa_3(BP_n)=2n-1\) and \(c\kappa_4(BP_n)=3n-2\) for \(n\geqslant 4\), and \(c\kappa_5(BP_n)=4n-4\) for \(n\geqslant 5\).