<p>High-performance computing extensively depends on parallel and distributed systems, necessitating the establishment of quantitative parameters to evaluate the fault tolerability of interconnection networks. The topological structures of interconnection networks in some parallel and distributed systems are designed as <i>n</i>-dimensional <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\((K_{9}-C_{9})^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>9</mn> </msub> <mo>-</mo> <msub> <mi>C</mi> <mn>9</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation>, obtained through the repeatedly application of the <i>n</i>-th Cartesian product operation. Since the <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation>-conditional edge-connectivity is proposed by Harary, as a parameter for evaluating the link fault tolerability of the underlying topology graph of the interconnection network system, it has been widely studied in many interconnection networks. The <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation>-conditional edge-connectivity of a connected graph <i>G</i>, denoted by <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda (\mathcal {P};G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>λ</mi> <mo stretchy="false">(</mo> <mi mathvariant="script">P</mi> <mo>;</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, if any, describes the minimum cardinality of the fault edge-cut of the graph <i>G</i>, whose malfunction divides <i>G</i> into multiple components, with each component satisfying a given property <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> of the graph. In this paper, we primarily define <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}_{i}^{t}\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="script">P</mi> <mrow> <mi>i</mi> </mrow> <mi>t</mi> </msubsup> </math></EquationSource> </InlineEquation> to be properties of containing at least <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(9^t\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>9</mn> <mi>t</mi> </msup> </math></EquationSource> </InlineEquation> processors, every remaining processor lying in a lower dimensional subnetwork of the <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\((K_{9}-C_{9})^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>9</mn> </msub> <mo>-</mo> <msub> <mi>C</mi> <mn>9</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq11.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">\((K_{9}-C_{9})^{t}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>9</mn> </msub> <mo>-</mo> <msub> <mi>C</mi> <mn>9</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mi>t</mi> </msup> </math></EquationSource> </InlineEquation>, having a minimum degree or average degree of at least 6<i>t</i>, existing two components with each component having at least <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(9^t\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>9</mn> <mi>t</mi> </msup> </math></EquationSource> </InlineEquation> processors, and containing at least one cycle, respectively. We use the properties of the optimal solution to the edge isoperimetric problem of <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\((K_{9}-C_{9})^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>9</mn> </msub> <mo>-</mo> <msub> <mi>C</mi> <mn>9</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> and find that the exact values of the <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq14.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}_{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>-conditional edge-connectivities of the graph <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq15.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\((K_{9}-C_{9})^{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>9</mn> </msub> <mo>-</mo> <msub> <mi>C</mi> <mn>9</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> share a common value of <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq16.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(6(n-t)9^t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>6</mn> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mn>9</mn> <mi>t</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq17.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\(1\le i\le 5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq18.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="101" /> </InlineMediaObject> <EquationSource Format="TEX">\(0\le t\le n-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>t</mi> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, except for <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq19.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">\(i=6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>=</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>, the value is <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1273_Article_IEq20.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(18n - 6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>18</mn> <mi>n</mi> <mo>-</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Link fault tolerability of the Cartesian product power graph \((K_{9}-C_{9})^{n}\): conditional edge-connectivities under six link fault patterns

  • Zhaoman Huang,
  • Yayu Yang,
  • Mingzu Zhang,
  • Weihua Yang

摘要

High-performance computing extensively depends on parallel and distributed systems, necessitating the establishment of quantitative parameters to evaluate the fault tolerability of interconnection networks. The topological structures of interconnection networks in some parallel and distributed systems are designed as n-dimensional \((K_{9}-C_{9})^{n}\) ( K 9 - C 9 ) n , obtained through the repeatedly application of the n-th Cartesian product operation. Since the \(\mathcal {P}\) P -conditional edge-connectivity is proposed by Harary, as a parameter for evaluating the link fault tolerability of the underlying topology graph of the interconnection network system, it has been widely studied in many interconnection networks. The \(\mathcal {P}\) P -conditional edge-connectivity of a connected graph G, denoted by \(\lambda (\mathcal {P};G)\) λ ( P ; G ) , if any, describes the minimum cardinality of the fault edge-cut of the graph G, whose malfunction divides G into multiple components, with each component satisfying a given property \(\mathcal {P}\) P of the graph. In this paper, we primarily define \(\mathcal {P}_{i}^{t}\) P i t to be properties of containing at least \(9^t\) 9 t processors, every remaining processor lying in a lower dimensional subnetwork of the \((K_{9}-C_{9})^{n}\) ( K 9 - C 9 ) n , \((K_{9}-C_{9})^{t}\) ( K 9 - C 9 ) t , having a minimum degree or average degree of at least 6t, existing two components with each component having at least \(9^t\) 9 t processors, and containing at least one cycle, respectively. We use the properties of the optimal solution to the edge isoperimetric problem of \((K_{9}-C_{9})^{n}\) ( K 9 - C 9 ) n and find that the exact values of the \(\mathcal {P}_{i}\) P i -conditional edge-connectivities of the graph \((K_{9}-C_{9})^{n}\) ( K 9 - C 9 ) n share a common value of \(6(n-t)9^t\) 6 ( n - t ) 9 t for \(1\le i\le 5\) 1 i 5 and \(0\le t\le n-1\) 0 t n - 1 , except for \(i=6\) i = 6 , the value is \(18n - 6\) 18 n - 6 .