Star structure connectivities of pancake graphs and burnt pancake graphs

Abstract

Let H be a connected subgraph of a graph G. The H-structure connectivity $\kappa (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 ${\kappa }^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 $\kappa (P_n;K_{1,t_1})={\kappa }^s(P_n;K_{1,t_1})=n-1(1\le t_1\le n-2)$, and $\kappa (B{P}_n;K_{1,t_2})={\kappa }^s(B{P}_n;K_{1,t_2})=n(1\le t_2\le n-1)$.

Keywords:

• Star-structure connectivity
• star-substructure connectivity
• pancake graphs
• burnt pancake graphs
• Fault tolerance

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The research is supported by NSFXJ (Nos. 2020D04046 and 2021D01C116).