<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> be a connected subgraph of a graph <i>G</i>. The <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-structure connectivity of <i>G</i>, denoted by <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">\( \kappa (G;{\mathcal {H}}) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi mathvariant="script">H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is the minimum cardinality of a set of connected subgraphs in <i>G</i>, whose removal either disconnects <i>G</i> or reduces it to a trivial graph, where each element in the set is isomorphic to <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>. The <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-substructure connectivity of <i>G</i>, denoted by <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">\( \kappa ^s(G;{\mathcal {H}}) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi mathvariant="script">H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the minimum cardinality of a set of connected subgraphs in <i>G</i>, whose removal either disconnects <i>G</i> or reduces it to a trivial graph, where each element in the set is isomorphic to a connected subgraph of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>. In this paper, we investigate the <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq8.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-structure connectivity and <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-substructure connectivity of folded divide-and-swap cube <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">\( FDSC_n \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq11.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="275" /> </InlineMediaObject> <EquationSource Format="TEX">\( {\mathcal {H}}\in \{K_1, K_{1,1}, K_{1,m} \text (2\le m \le d+2) \} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">H</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>m</mi> </mrow> </msub> <mtext>(</mtext> <mn>2</mn> <mo>≤</mo> <mi>m</mi> <mo>≤</mo> <mi>d</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq12.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\( n=2^d \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <msup> <mn>2</mn> <mi>d</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>. We show that <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="305" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (FDSC_n;K_1)=\kappa ^s(FDSC_n;K_1)=d+2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>d</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq14.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="323" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (FDSC_n;K_{1,1})=\kappa ^s(FDSC_n;K_{1,1})=d+1 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq15.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\( d\ge 3 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq16.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="347" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (FDSC_n;K_{1,m})=\kappa ^s(FDSC_n;K_{1,m})=\lfloor \frac{d}{2}\rfloor +1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>m</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>m</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>d</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq17.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\ge 1 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq18.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="107" /> </InlineMediaObject> <EquationSource Format="TEX">\( 2\le m \le d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>≤</mo> <mi>m</mi> <mo>≤</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Moreover, we show that <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq19.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="214" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa ^s(FDSC_n;K_{1,d+2})=\lfloor \frac{d}{2}\rfloor +1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>d</mi> <mo>+</mo> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>d</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq20.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\ge 1 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and we provide a bound for <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq21.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="134" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (FDSC_n;K_{1,d+2})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mi>D</mi> <mi>S</mi> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>d</mi> <mo>+</mo> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq22"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7100_Article_IEq22.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\ge 3 \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Muhammed Türkmen,
  • Canan Çiftçi,
  • Gülnaz Boruzanlı Ekinci

摘要

Let \( {\mathcal {H}} \) H be a connected subgraph of a graph G. The \({\mathcal {H}}\) H -structure connectivity of G, denoted by \( \kappa (G;{\mathcal {H}}) \) κ ( G ; H ) , 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}} \) H . The \({\mathcal {H}}\) H -substructure connectivity of G, denoted by \( \kappa ^s(G;{\mathcal {H}}) \) κ s ( G ; H ) , 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}} \) H . In this paper, we investigate the \( {\mathcal {H}} \) H -structure connectivity and \( {\mathcal {H}} \) H -substructure connectivity of folded divide-and-swap cube \( FDSC_n \) F D S C n for \( {\mathcal {H}}\in \{K_1, K_{1,1}, K_{1,m} \text (2\le m \le d+2) \} \) H { K 1 , K 1 , 1 , K 1 , m ( 2 m d + 2 ) } where \( n=2^d \) n = 2 d . We show that \(\kappa (FDSC_n;K_1)=\kappa ^s(FDSC_n;K_1)=d+2\) κ ( F D S C n ; K 1 ) = κ s ( F D S C n ; K 1 ) = d + 2 , \(\kappa (FDSC_n;K_{1,1})=\kappa ^s(FDSC_n;K_{1,1})=d+1 \) κ ( F D S C n ; K 1 , 1 ) = κ s ( F D S C n ; K 1 , 1 ) = d + 1 for \( d\ge 3 \) d 3 and \(\kappa (FDSC_n;K_{1,m})=\kappa ^s(FDSC_n;K_{1,m})=\lfloor \frac{d}{2}\rfloor +1\) κ ( F D S C n ; K 1 , m ) = κ s ( F D S C n ; K 1 , m ) = d 2 + 1 for \(d\ge 1 \) d 1 and \( 2\le m \le d+1\) 2 m d + 1 . Moreover, we show that \(\kappa ^s(FDSC_n;K_{1,d+2})=\lfloor \frac{d}{2}\rfloor +1\) κ s ( F D S C n ; K 1 , d + 2 ) = d 2 + 1 for \(d\ge 1 \) d 1 and we provide a bound for \(\kappa (FDSC_n;K_{1,d+2})\) κ ( F D S C n ; K 1 , d + 2 ) when \(d\ge 3 \) d 3 .