Star structure connectivities of pancake graphs and burnt pancake graphs. Issue 5 (3rd September 2021) - Dilixiati, Subinur; Sabir, Eminjan; Meng, Jixiang
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 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 ) .