<p>Let <i>G</i> be a connected simple graph with vertex set <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(V\left( G \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> and edge set <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(E\left( G \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ω</mi> </math></EquationSource> </InlineEquation> be a subset of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(V\left( G \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> with at least two vertices. A path containing all vertices of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ω</mi> </math></EquationSource> </InlineEquation> is said to be an <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq6.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega \text{- } \text {path}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mtext>- path</mtext> </mrow> </math></EquationSource> </InlineEquation> of <i>G</i>. Two <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega \text{- }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mtext>-</mtext> <mspace width="0.333333em" /> </mrow> </math></EquationSource> </InlineEquation>paths <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\({{P}_{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\({{P}_{2}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> of <i>G</i> are internally disjoint if <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="150" /> </InlineMediaObject> <EquationSource Format="TEX">\(E\left( {{P}_{1}} \right) \cap E\left( {{P}_{2}} \right) =\varnothing \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mfenced close=")" open="("> <msub> <mi>P</mi> <mn>1</mn> </msub> </mfenced> <mo>∩</mo> <mi>E</mi> <mfenced close=")" open="("> <msub> <mi>P</mi> <mn>2</mn> </msub> </mfenced> <mo>=</mo> <mi>∅</mi> </mrow> </math></EquationSource> </InlineEquation>. For an integer <i>k</i> with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, the <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq12.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="151" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \text{- } \text {path} \text{- } \text {connectivity}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mtext>- path- connectivity</mtext> </mrow> </math></EquationSource> </InlineEquation> <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\({{\Pi }_{k}}\left( G \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Π</mi> <mi>k</mi> </msub> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> is defined as <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq14.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="352" /> </InlineMediaObject> <EquationSource Format="TEX">\({{\Pi }_{k}}\left( G \right) =\min \left\{ {{\Pi }_{k}}\left( \Omega \right) \left| \, \Omega \subseteq V\left( G \right) \text { and }\left| \, \Omega \right| =k \right. \right\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Π</mi> <mi>k</mi> </msub> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>=</mo> <mo movablelimits="true">min</mo> <mfenced close="}" open="{"> <msub> <mi mathvariant="normal">Π</mi> <mi>k</mi> </msub> <mfenced close=")" open="("> <mi mathvariant="normal">Ω</mi> </mfenced> <mfenced open="|"> <mspace width="0.166667em" /> <mi mathvariant="normal">Ω</mi> <mo>⊆</mo> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mspace width="0.333333em" /> <mtext>and</mtext> <mspace width="0.333333em" /> <mfenced close="|" open="|"> <mspace width="0.166667em" /> <mi mathvariant="normal">Ω</mi> </mfenced> <mo>=</mo> <mi>k</mi> </mfenced> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq15.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\({{\Pi }_{k}}\left( \Omega \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Π</mi> <mi>k</mi> </msub> <mfenced close=")" open="("> <mi mathvariant="normal">Ω</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> represents the maximum number of internally disjoint <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq16.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega \text{- } \text {paths}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mtext>- paths</mtext> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we determine the <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq17.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="149" /> </InlineMediaObject> <EquationSource Format="TEX">\(3 \text{- } \text {path} \text{- } \text {connectivity}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mtext>- path- connectivity</mtext> </mrow> </math></EquationSource> </InlineEquation> of the <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq18.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="106" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \text{- } \text {dimensional}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mtext>- dimensional</mtext> </mrow> </math></EquationSource> </InlineEquation> folded hypercubes <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq19.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">\(F{{Q}_{n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and prove that <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq20.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="186" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Pi _3\left( FQ_n \right) =\lfloor \frac{3\left( n+1 \right) -1}{4} \rfloor \text { for }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Π</mi> <mn>3</mn> </msub> <mfenced close=")" open="("> <mi>F</mi> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mfenced> <mo>=</mo> <mrow> <mo>⌊</mo> <mfrac> <mrow> <mn>3</mn> <mfenced close=")" open="("> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mfenced> <mo>-</mo> <mn>1</mn> </mrow> <mn>4</mn> </mfrac> <mo>⌋</mo> </mrow> <mspace width="0.333333em" /> <mtext>for</mtext> <mspace width="0.333333em" /> </mrow> </math></EquationSource> </InlineEquation> all <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7558_Article_IEq21.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\geqslant 2.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩾</mo> <mn>2</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

The 3-path connectivity of the folded hypercube

  • Yi Wang,
  • Dongqin Cheng

摘要

Let G be a connected simple graph with vertex set \(V\left( G \right) \) V G and edge set \(E\left( G \right) \) E G . Let \(\Omega \) Ω be a subset of \(V\left( G \right) \) V G with at least two vertices. A path containing all vertices of \(\Omega \) Ω is said to be an \(\Omega \text{- } \text {path}\) Ω - path of G. Two \(\Omega \text{- }\) Ω - paths \({{P}_{1}}\) P 1 and \({{P}_{2}}\) P 2 of G are internally disjoint if \(E\left( {{P}_{1}} \right) \cap E\left( {{P}_{2}} \right) =\varnothing \) E P 1 E P 2 = . For an integer k with \(k\ge 2\) k 2 , the \(k \text{- } \text {path} \text{- } \text {connectivity}\) k - path- connectivity \({{\Pi }_{k}}\left( G \right) \) Π k G is defined as \({{\Pi }_{k}}\left( G \right) =\min \left\{ {{\Pi }_{k}}\left( \Omega \right) \left| \, \Omega \subseteq V\left( G \right) \text { and }\left| \, \Omega \right| =k \right. \right\} \) Π k G = min Π k Ω Ω V G and Ω = k , where \({{\Pi }_{k}}\left( \Omega \right) \) Π k Ω represents the maximum number of internally disjoint \(\Omega \text{- } \text {paths}\) Ω - paths . In this paper, we determine the \(3 \text{- } \text {path} \text{- } \text {connectivity}\) 3 - path- connectivity of the \(n \text{- } \text {dimensional}\) n - dimensional folded hypercubes \(F{{Q}_{n}}\) F Q n and prove that \(\Pi _3\left( FQ_n \right) =\lfloor \frac{3\left( n+1 \right) -1}{4} \rfloor \text { for }\) Π 3 F Q n = 3 n + 1 - 1 4 for all \(n\geqslant 2.\) n 2 .