Star structure connectivities of pancake graphs and burnt pancake graphs
Subinur Dilixiati, Eminjan Sabir, Jixiang Meng
Abstract
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 Pn and BPn be the n-dimensional pancake graph and n-dimensional burnt pancake graph, respectively. In this paper we show κ(Pn;K1,t1)=κs(Pn;K1,t1)=n−1(1≤t1≤n−2), and κ(BPn;K1,t2)=κs(BPn;K1,t2)=n(1≤t2≤n−1).