<p>For a graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation>, a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-regular edge cut is an edge subset <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(S \subseteq E(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G-S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> is disconnected and each connected component of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(G-S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> is a <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-regular graph. The <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-regular edge-connectivity is defined as the minimum cardinality among all <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-regular edge cuts. The <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(h\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>h</mi> </math></EquationSource> </InlineEquation>-extra <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(r\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>r</mi> </math></EquationSource> </InlineEquation>-component edge-connectivity <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(c\lambda _r^h(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msubsup> <mi>λ</mi> <mi>r</mi> <mi>h</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> is the minimum cardinality among all edge subsets <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(F \subseteq E(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>⊆</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, if any, such that <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(G-F\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> has exactly <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(r\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>r</mi> </math></EquationSource> </InlineEquation> components and each component has at least <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(h\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>h</mi> </math></EquationSource> </InlineEquation> vertices. In this paper, we determine that the <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(h\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>h</mi> </math></EquationSource> </InlineEquation>-extra 5-component edge-connectivity of <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\({FQ}_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="italic">FQ</mi> </mrow> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(c\lambda _5^h(FQ_{n})={4nh-4ex_h(FQ_n)}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msubsup> <mi>λ</mi> <mn>5</mn> <mi>h</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mn>4</mn> <mi>n</mi> <mi>h</mi> <mo>-</mo> <mn>4</mn> <mi>e</mi> <msub> <mi>x</mi> <mi>h</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>F</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(n\ge 6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(1\le h\le 2^{\lfloor \frac{n}{2}\rfloor -2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>h</mi> <mo>≤</mo> <msup> <mn>2</mn> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> <mo>-</mo> <mn>2</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. In addition, we derive the <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-regular edge-connectivities of the folded hypercubes <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\({FQ}_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="italic">FQ</mi> </mrow> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and the hierarchical folded cubes <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\({HFQ}_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="italic">HFQ</mi> </mrow> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> as follows: <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(\lambda ^{kr}({FQ}_n) = 2^{n-1}(n+1-k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>λ</mi> <mrow> <mi mathvariant="italic">kr</mi> </mrow> </msup> <mrow> <mo stretchy="false">(</mo> <msub> <mrow> <mi mathvariant="italic">FQ</mi> </mrow> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo>-</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(n \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(1 \le k \le n-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>; <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(\lambda ^{kr}({HFQ}_n) = 2^{2n-1}(n+2-k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>λ</mi> <mrow> <mi mathvariant="italic">kr</mi> </mrow> </msup> <mrow> <mo stretchy="false">(</mo> <msub> <mrow> <mi mathvariant="italic">HFQ</mi> </mrow> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mn>2</mn> <mrow> <mn>2</mn> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo>-</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq29"> <EquationSource Format="TEX">\(n \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq30"> <EquationSource Format="TEX">\(1 \le k \le n + 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

The conditional edge-connectivity of folded hypercubes and hierarchical folded cubes

  • Li Wang,
  • Haohui Zhang,
  • Tingshi Wang,
  • Yuyan Wang

摘要

For a graph \(G\) G , a \(k\) k -regular edge cut is an edge subset \(S \subseteq E(G)\) S E ( G ) such that \(G-S\) G - S is disconnected and each connected component of \(G-S\) G - S is a \(k\) k -regular graph. The \(k\) k -regular edge-connectivity is defined as the minimum cardinality among all \(k\) k -regular edge cuts. The \(h\) h -extra \(r\) r -component edge-connectivity \(c\lambda _r^h(G)\) c λ r h ( G ) of \(G\) G is the minimum cardinality among all edge subsets \(F \subseteq E(G)\) F E ( G ) , if any, such that \(G-F\) G - F has exactly \(r\) r components and each component has at least \(h\) h vertices. In this paper, we determine that the \(h\) h -extra 5-component edge-connectivity of \({FQ}_n\) FQ n is \(c\lambda _5^h(FQ_{n})={4nh-4ex_h(FQ_n)}\) c λ 5 h ( F Q n ) = 4 n h - 4 e x h ( F Q n ) when \(n\ge 6\) n 6 and \(1\le h\le 2^{\lfloor \frac{n}{2}\rfloor -2}\) 1 h 2 n 2 - 2 . In addition, we derive the \(k\) k -regular edge-connectivities of the folded hypercubes \({FQ}_n\) FQ n and the hierarchical folded cubes \({HFQ}_n\) HFQ n as follows: \(\lambda ^{kr}({FQ}_n) = 2^{n-1}(n+1-k)\) λ kr ( FQ n ) = 2 n - 1 ( n + 1 - k ) for \(n \ge 2\) n 2 and \(1 \le k \le n-1\) 1 k n - 1 ; \(\lambda ^{kr}({HFQ}_n) = 2^{2n-1}(n+2-k)\) λ kr ( HFQ n ) = 2 2 n - 1 ( n + 2 - k ) for \(n \ge 2\) n 2 and \(1 \le k \le n + 1\) 1 k n + 1 .