<p>The study of conditional connectivity has certain limitations in characterizing fault tolerance, as it often fails to fully account for the structural relationship between adjacent processors in multiprocessor systems. To address this issue, two indicators, namely the <i>R</i>-structure connectivity and the <i>R</i>-substructure connectivity, have been proposed in the literature to better measure the fault tolerance of interconnection networks. Let <i>G</i> be a connected graph, and <i>R</i>, <i>M</i> be two connected subgraphs of <i>G</i>. The <i>R</i>-structure (resp. <i>R</i>-substructure) connectivity, denoted by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\kappa (G;R)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>R</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (resp. <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\kappa ^{s}(G;R)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>κ</mi> <mi>s</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>R</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>), is the cardinality of a minimum set of subgraphs <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathcal {F}=\{F_{1},\cdots ,F_{t}\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>F</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> in <i>G</i> such that every <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(F_{i}\in \mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>i</mi> </msub> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> is isomorphic to <i>R</i> (resp. to a connected subgraph of <i>R</i>) and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(G-F\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> is disconnected. In particular, we call <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> a minimum <i>R</i>-structure (resp. <i>R</i>-substructure) cut of <i>G</i>. Moreover, <i>G</i> is called hyper (sub-)<InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(R|_{M}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi>R</mi> <mo stretchy="false">|</mo> </mrow> <mi>M</mi> </msub> </math></EquationSource> </InlineEquation>-connected if the removal of every minimum <i>R</i>-structure (<i>R</i>-substructure) cut divides <i>G</i> into exactly two components, one of which is isomorphic to <i>M</i>. In this paper, the <i>R</i>-structure connectivity and the <i>R</i>-substructure connectivity of hierarchical pancake networks <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(HPG_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mi>P</mi> <msub> <mi>G</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(n\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> are studied for the first time, where <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(R\in \{K_{1,r}\mid 1\le r\le n-1\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>r</mi> </mrow> </msub> <mo>∣</mo> <mn>1</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, we prove that <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(HPG_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mi>P</mi> <msub> <mi>G</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is both hyper <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(R|_{K_{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi>R</mi> <mo stretchy="false">|</mo> </mrow> <msub> <mi>K</mi> <mn>1</mn> </msub> </msub> </math></EquationSource> </InlineEquation>-connected and hyper sub-<InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(R|_{K_{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi>R</mi> <mo stretchy="false">|</mo> </mrow> <msub> <mi>K</mi> <mn>1</mn> </msub> </msub> </math></EquationSource> </InlineEquation>-connected for <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(n\ge 4.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>4</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

Hyper star structure connectivity of hierarchical pancake networks

  • Liqing Lin,
  • Li Wang,
  • Yanxia Zhao

摘要

The study of conditional connectivity has certain limitations in characterizing fault tolerance, as it often fails to fully account for the structural relationship between adjacent processors in multiprocessor systems. To address this issue, two indicators, namely the R-structure connectivity and the R-substructure connectivity, have been proposed in the literature to better measure the fault tolerance of interconnection networks. Let G be a connected graph, and R, M be two connected subgraphs of G. The R-structure (resp. R-substructure) connectivity, denoted by \(\kappa (G;R)\) κ ( G ; R ) (resp. \(\kappa ^{s}(G;R)\) κ s ( G ; R ) ), is the cardinality of a minimum set of subgraphs \(\mathcal {F}=\{F_{1},\cdots ,F_{t}\}\) F = { F 1 , , F t } in G such that every \(F_{i}\in \mathcal {F}\) F i F is isomorphic to R (resp. to a connected subgraph of R) and \(G-F\) G - F is disconnected. In particular, we call \(\mathcal {F}\) F a minimum R-structure (resp. R-substructure) cut of G. Moreover, G is called hyper (sub-) \(R|_{M}\) R | M -connected if the removal of every minimum R-structure (R-substructure) cut divides G into exactly two components, one of which is isomorphic to M. In this paper, the R-structure connectivity and the R-substructure connectivity of hierarchical pancake networks \(HPG_{n}\) H P G n for \(n\ge 3\) n 3 are studied for the first time, where \(R\in \{K_{1,r}\mid 1\le r\le n-1\}\) R { K 1 , r 1 r n - 1 } . Furthermore, we prove that \(HPG_{n}\) H P G n is both hyper \(R|_{K_{1}}\) R | K 1 -connected and hyper sub- \(R|_{K_{1}}\) R | K 1 -connected for \(n\ge 4.\) n 4 .