<p>The <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(FTCQ_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, an <i>n</i>-dimensional folded twisted crossed cube proposed by Guo, is derived from the twisted crossed cube <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(TCQ_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> by including an additional set of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2^{n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> edges. The <i>h</i>-extra connectivity of a connected graph <i>G</i>, denoted by <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\kappa _{h}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>κ</mi> <mi>h</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the minimum number of vertices that need to be removed in order to disconnect <i>G</i>, while ensuring that the remaining graph contains no fewer than <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(h+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> vertices. The <i>h</i>-extra diagnosability of a graph <i>G</i> requires that each fault-free component of <i>G</i> must contain no fewer than <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(h+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> vertices. The <i>h</i>-extra diagnosability of a graph <i>G</i> is denoted as <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(t_{h}^{PMC}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mrow> <mi>h</mi> </mrow> <mrow> <mi mathvariant="italic">PMC</mi> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> under the PMC model and as <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(t_{h}^{MM^*}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mrow> <mi>h</mi> </mrow> <mrow> <mi>M</mi> <msup> <mi>M</mi> <mo>∗</mo> </msup> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> under the MM<InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(^*\)</EquationSource> <EquationSource Format="MATHML"><math> <mmultiscripts> <mrow /> <mrow /> <mo>∗</mo> </mmultiscripts> </math></EquationSource> </InlineEquation> model. In this paper, we determine the <i>h</i>-extra connectivity of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(TCQ_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\kappa _{h}(TCQ_{n})=n(h+1)-\frac{1}{2}h^{2}-\frac{3}{2}h\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>κ</mi> <mi>h</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>n</mi> <mrow> <mo stretchy="false">(</mo> <mi>h</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msup> <mi>h</mi> <mn>2</mn> </msup> <mo>-</mo> <mfrac> <mn>3</mn> <mn>2</mn> </mfrac> <mi>h</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(n\ge 5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(0\le h \le \lfloor \frac{n}{2} \rfloor\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>, and the <i>h</i>-extra diagnosability of <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(TCQ_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(t_{h}^{PMC}(TCQ_{n})=(n+1)h-\frac{1}{2}h^{2}-\frac{1}{2}h\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mrow> <mi>h</mi> </mrow> <mrow> <mi mathvariant="italic">PMC</mi> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>h</mi> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msup> <mi>h</mi> <mn>2</mn> </msup> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mi>h</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(n\ge 5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(0\le h \le \lfloor \frac{n}{2} \rfloor\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>, under the PMC model, and <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(t_{h}^{MM^*}(TCQ_{n})=n(h+1)-\frac{1}{2}h^{2}-\frac{1}{2}h\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mrow> <mi>h</mi> </mrow> <mrow> <mi>M</mi> <msup> <mi>M</mi> <mo>∗</mo> </msup> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>n</mi> <mrow> <mo stretchy="false">(</mo> <mi>h</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msup> <mi>h</mi> <mn>2</mn> </msup> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mi>h</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(n \ge 6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(0 \le h\le \frac{1}{2}(n-2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> under the MM<InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(^{*}\)</EquationSource> <EquationSource Format="MATHML"><math> <mmultiscripts> <mrow /> <mrow /> <mrow> <mrow /> <mo>∗</mo> </mrow> </mmultiscripts> </math></EquationSource> </InlineEquation> model. Furthermore, we investigate the <i>h</i>-extra connectivity of <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(FTCQ_{n+1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(\kappa _{h}(FTCQ_{n+1})=(n+2)(h+1)-\frac{1}{2}h^{2}-\frac{3}{2}h\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>κ</mi> <mi>h</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>h</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msup> <mi>h</mi> <mn>2</mn> </msup> <mo>-</mo> <mfrac> <mn>3</mn> <mn>2</mn> </mfrac> <mi>h</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(n \ge 7\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(0\le h \le \lfloor \frac{n}{2}\rfloor\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>, and the <i>h</i>-extra diagnosability of <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(FTCQ_{n+1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(t_{h}^{PMC}(FTCQ_{n+1})=(n+2)(h+1)-\frac{1}{2}h^{2}-\frac{1}{2}h\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mrow> <mi>h</mi> </mrow> <mrow> <mi mathvariant="italic">PMC</mi> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <mi>T</mi> <mi>C</mi> <msub> <mi>Q</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>h</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msup> <mi>h</mi> <mn>2</mn> </msup> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mi>h</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(n\ge 7\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq29"> <EquationSource Format="TEX">\(0\le h \le \lfloor \frac{n}{2} \rfloor\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>, under the PMC model.</p>

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

Fault tolerability analysis of twisted crossed cubes and folded twisted crossed cubes based on h-extra fault pattern

  • Xuepeng Cai,
  • Mingzu Zhang,
  • Zhaoman Huang

摘要

The \(FTCQ_{n}\) F T C Q n , an n-dimensional folded twisted crossed cube proposed by Guo, is derived from the twisted crossed cube \(TCQ_n\) T C Q n by including an additional set of \(2^{n-1}\) 2 n - 1 edges. The h-extra connectivity of a connected graph G, denoted by \(\kappa _{h}(G)\) κ h ( G ) , is the minimum number of vertices that need to be removed in order to disconnect G, while ensuring that the remaining graph contains no fewer than \(h+1\) h + 1 vertices. The h-extra diagnosability of a graph G requires that each fault-free component of G must contain no fewer than \(h+1\) h + 1 vertices. The h-extra diagnosability of a graph G is denoted as \(t_{h}^{PMC}(G)\) t h PMC ( G ) under the PMC model and as \(t_{h}^{MM^*}(G)\) t h M M ( G ) under the MM \(^*\) model. In this paper, we determine the h-extra connectivity of \(TCQ_{n}\) T C Q n is \(\kappa _{h}(TCQ_{n})=n(h+1)-\frac{1}{2}h^{2}-\frac{3}{2}h\) κ h ( T C Q n ) = n ( h + 1 ) - 1 2 h 2 - 3 2 h for \(n\ge 5\) n 5 , \(0\le h \le \lfloor \frac{n}{2} \rfloor\) 0 h n 2 , and the h-extra diagnosability of \(TCQ_{n}\) T C Q n is \(t_{h}^{PMC}(TCQ_{n})=(n+1)h-\frac{1}{2}h^{2}-\frac{1}{2}h\) t h PMC ( T C Q n ) = ( n + 1 ) h - 1 2 h 2 - 1 2 h for \(n\ge 5\) n 5 , \(0\le h \le \lfloor \frac{n}{2} \rfloor\) 0 h n 2 , under the PMC model, and \(t_{h}^{MM^*}(TCQ_{n})=n(h+1)-\frac{1}{2}h^{2}-\frac{1}{2}h\) t h M M ( T C Q n ) = n ( h + 1 ) - 1 2 h 2 - 1 2 h for \(n \ge 6\) n 6 , \(0 \le h\le \frac{1}{2}(n-2)\) 0 h 1 2 ( n - 2 ) under the MM \(^{*}\) model. Furthermore, we investigate the h-extra connectivity of \(FTCQ_{n+1}\) F T C Q n + 1 is \(\kappa _{h}(FTCQ_{n+1})=(n+2)(h+1)-\frac{1}{2}h^{2}-\frac{3}{2}h\) κ h ( F T C Q n + 1 ) = ( n + 2 ) ( h + 1 ) - 1 2 h 2 - 3 2 h for \(n \ge 7\) n 7 , \(0\le h \le \lfloor \frac{n}{2}\rfloor\) 0 h n 2 , and the h-extra diagnosability of \(FTCQ_{n+1}\) F T C Q n + 1 is \(t_{h}^{PMC}(FTCQ_{n+1})=(n+2)(h+1)-\frac{1}{2}h^{2}-\frac{1}{2}h\) t h PMC ( F T C Q n + 1 ) = ( n + 2 ) ( h + 1 ) - 1 2 h 2 - 1 2 h for \(n\ge 7\) n 7 , \(0\le h \le \lfloor \frac{n}{2} \rfloor\) 0 h n 2 , under the PMC model.