Structure and substructure connectivity of folded divide-and-swap cube

Abstract Let $$ {\mathcal {H}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> be a connected subgraph of a graph G . The $${\mathcal {H}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> -structure connectivity of G , denoted by $$ \kappa (G;{\mathcal {H}}) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>;</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , is the minimum cardinality of a set of connected subgraphs in G , whose removal either disconnects G or reduces it to a trivial graph, where each element in the set is isomorphic to $$ {\mathcal {H}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> . The $${\mathcal {H}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> -substructure connectivity of G , denoted by $$ \kappa ^s(G;{\mathcal {H}}) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>κ</mml:mi> <mml:mi>s</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>;</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , is the minimum cardinality of a set of connected subgraphs in G , whose removal either disconnects G or reduces it to a trivial graph, where each element in the set is isomorphic to a connected subgraph of $$ {\mathcal {H}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> . In this paper, we investigate the $$ {\mathcal {H}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> -structure connectivity and $$ {\mathcal {H}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> -substructure connectivity of folded divide-and-swap cube $$ FDSC_n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mi>D</mml:mi> <mml:mi>S</mml:mi> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> for $$ {\mathcal {H}}\in \{K_1, K_{1,1}, K_{1,m} \text (2\le m \le d+2) \} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>{</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:msub> <mml:mtext>(</mml:mtext> <mml:mn>2</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>m</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> where $$ n=2^d $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>d</mml:mi> </mml:msup> </mml:mrow> </mml:math> . We show that $$\kappa (FDSC_n;K_1)=\kappa ^s(FDSC_n;K_1)=d+2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mi>D</mml:mi> <mml:mi>S</mml:mi> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>;</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>κ</mml:mi> <mml:mi>s</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mi>D</mml:mi> <mml:mi>S</mml:mi> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>;</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , $$\kappa (FDSC_n;K_{1,1})=\kappa ^s(FDSC_n;K_{1,1})=d+1 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mi>D</mml:mi>