Star structure connectivities of pancake graphs and burnt pancake graphs.

Let H be a connected subgraph of a graph G. The H-structure connectivity κ (G ; H) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to H. Similarly, the H-substructure connectivity κ s (G ; H) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of H. Structure connectivity and substructure connectivity generalise the classic connectivity. Let P n and B P n be the n-dimensional pancake graph and n-dimensional burnt pancake graph, respectively. In this paper we show κ (P n ; K 1 , t 1 ) = κ s (P n ; K 1 , t 1 ) = n − 1 (1 ≤ t 1 ≤ n − 2) , and κ (B P n ; K 1 , t 2 ) = κ s (B P n ; K 1 , t 2 ) = n (1 ≤ t 2 ≤ n − 1). [ABSTRACT FROM AUTHOR]