The <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-component connectivity of a graph G, denoted by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$c\kappa _{\ell }(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msub> <mi>κ</mi> <mi>ℓ</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 whose removal from G results in a disconnected graph with at least <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> components. The hierarchical pancake graph <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$HP_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is a newly proposed interconnection topology, which uses the pancake graphs as building blocks. In the paper, we study the <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-component connectivity of hierarchical pancake graph <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$HP_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and determine the <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-component connectivity <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$c\kappa _{\ell }(HP_{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msub> <mi>κ</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>H</mi> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7542_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="105" /> </InlineMediaObject> <EquationSource Format="TEX">$\ell \in \left\{ 2,3,4,5 \right\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>∈</mo> <mfenced close="}" open="{"> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>4</mn> <mo>,</mo> <mn>5</mn> </mfenced> </mrow> </math></EquationSource> </InlineEquation>.

Component connectivity of hierarchical pancake graphs

期刊论文
发表日期：

2025年6月16日

查看全文

Hui Liu,
Yingzhi Tian

摘要

The $\ell$ $ℓ$ -component connectivity of a graph G, denoted by $c\kappa _{\ell }(G)$ $c κ_{ℓ} (G)$ , is the minimum number of vertices whose removal from G results in a disconnected graph with at least $\ell$ $ℓ$ components. The hierarchical pancake graph $HP_{n}$ $H P_{n}$ is a newly proposed interconnection topology, which uses the pancake graphs as building blocks. In the paper, we study the $\ell$ $ℓ$ -component connectivity of hierarchical pancake graph $HP_{n}$ $H P_{n}$ and determine the $\ell$ $ℓ$ -component connectivity $c\kappa _{\ell }(HP_{n})$ $c κ_{ℓ} (H P_{n})$ for $\ell \in \left\{ 2,3,4,5 \right\}$ $ℓ \in \{2, 3, 4, 5\}$ .