Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs

The l-component connectivity of a graph G, denoted by c kappa(l) (G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least l components or a graph with fewer than l 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(l) (G) is an important issue on the research topic of networks. However, it has been pointed out in Hsu et al. (2012) that determining l-component connectivity is still unsolved in most interconnection networks even for small l's. Let BSn and BPn denote the n-dimensional bubble-sort star graph and the n-dimensional burnt pancake graph, respectively. In this paper, for BSn, we determine the values: c kappa(3)(BSn) = 4n - 9 for n >= 3, and c kappa(4)(BSn) = 6n - 16 and c kappa(5)(BSn) = 8n - 24 for n >= 4. Similarly, for BPn, we determine the values: c kappa(3)(BPn) = 2n - 1 and c kappa(4)(BPn) = 3n - 2 for n >= 4, and c kappa(5)(BPn) = 4n - 4 for n >= 5. (C) 2019 Elsevier B.V. All rights reserved.