<p>Large parallel computer systems bounding experience faults are inevitable due to their scale sizes, which poses serious reliability challenges for interconnection networks. Two new indicators were recently introduced to assess the stability of these networks more accurately, including structure connectivity and substructure connectivity. These parameters are crucial in measuring fault tolerance during chip failures. Let <i>H</i> be a certain graph pattern, and <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> be a set of subgraphs in a graph <i>G</i>. Then, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is called an <i>H</i>-structure cut (resp. <i>H</i>-substructure cut) of <i>G</i> if every element of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is isomorphic to <i>H</i> (resp. isomorphic to a connected subgraph of <i>H</i>) when <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(G-\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> is disconnected. The <i>H</i>-structure connectivity <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (G; H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (resp. <i>H</i>-substructure connectivity <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa ^s(G; 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>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>) is the minimum cardinality over all <i>H</i>-structure cuts (resp. <i>H</i>-substructure cuts). Recently, Ba, in her Ph.D. dissertation, posted the result of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="32" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{1,r}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>r</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-(sub)structure connectivity of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(FCQ_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq9.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(1\le r\le \frac{n}{2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(FCQ_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> denotes the <i>n</i>-dimensional folded crossed cube, which is a variant of the hypercube called crossed cube by enhancing a folded link between any two complementary vertices. In this paper, to supplement the completeness of the findings of this study, we successfully determine the <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="32" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{1,r}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>r</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-(sub)structure connectivity of <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(FCQ_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12190_2025_2372_Article_IEq13.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="104" /> </InlineMediaObject> <EquationSource Format="TEX">\(\frac{n}{2}+1\le r\le n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>+</mo> <mn>1</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, which solves the open problem proposed by Ba.</p>

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

Structure connectivity of folded crossed cubes based on faulty stars

  • Huimei Guo,
  • Rong-Xia Hao,
  • Aygul Mamut,
  • Jou-Ming Chang,
  • Jie Wu

摘要

Large parallel computer systems bounding experience faults are inevitable due to their scale sizes, which poses serious reliability challenges for interconnection networks. Two new indicators were recently introduced to assess the stability of these networks more accurately, including structure connectivity and substructure connectivity. These parameters are crucial in measuring fault tolerance during chip failures. Let H be a certain graph pattern, and \(\mathcal {F}\) F be a set of subgraphs in a graph G. Then, \(\mathcal {F}\) F is called an H-structure cut (resp. H-substructure cut) of G if every element of \(\mathcal {F}\) F is isomorphic to H (resp. isomorphic to a connected subgraph of H) when \(G-\mathcal {F}\) G - F is disconnected. The H-structure connectivity \(\kappa (G; H)\) κ ( G ; H ) (resp. H-substructure connectivity \(\kappa ^s(G; H)\) κ s ( G ; H ) ) is the minimum cardinality over all H-structure cuts (resp. H-substructure cuts). Recently, Ba, in her Ph.D. dissertation, posted the result of \(K_{1,r}\) K 1 , r -(sub)structure connectivity of \(FCQ_n\) F C Q n for \(1\le r\le \frac{n}{2}\) 1 r n 2 , where \(FCQ_n\) F C Q n denotes the n-dimensional folded crossed cube, which is a variant of the hypercube called crossed cube by enhancing a folded link between any two complementary vertices. In this paper, to supplement the completeness of the findings of this study, we successfully determine the \(K_{1,r}\) K 1 , r -(sub)structure connectivity of \(FCQ_n\) F C Q n for \(\frac{n}{2}+1\le r\le n\) n 2 + 1 r n , which solves the open problem proposed by Ba.