Let G be a simple connected graph with vertex set V(G) and edge set E(G). Let T be a subset of V(G) with cardinality <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$|T|\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>T</mi> <mo stretchy="false">|</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. A path connecting all vertices of T is called a T-path of G. Two T-paths <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$P_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$P_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> are <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\overline{T}$</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>T</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation>-disjoint if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$V(P_i)\cap V(P_j)=T$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∩</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>j</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>T</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$E(P_i)\cap E(P_j)=\emptyset$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∩</mo> <mi>E</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>j</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi mathvariant="normal">∅</mi> </mrow> </math></EquationSource> </InlineEquation>. Denote by <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\pi _G(T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>π</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> the maximum number of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\overline{T}$</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>T</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation>-disjoint paths in G. For an integer <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\ell \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, the <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\ell$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-path-connectivity <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\pi _\ell (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>π</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of G is formulated as <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\min \{\pi _G(T)\mid T\subseteq V(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <msub> <mi>π</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>∣</mo> <mi>T</mi> <mo>⊆</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$|T|=\ell \}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>T</mi> <mo stretchy="false">|</mo> <mo>=</mo> <mi>ℓ</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we study the 3-path-connectivity of the n-dimensional bubble-sort star graph <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$BS_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <msub> <mi>S</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. As a promising interconnection network topology for high-performance computing (HPC) systems, <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$BS_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <msub> <mi>S</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> possesses numerous superior properties. By deeply analyzing its structural characteristics, we show that <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\pi _3(BS_n)=\lfloor \frac{3n}{2}\rfloor -3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>π</mi> <mn>3</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>B</mi> <msub> <mi>S</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌊</mo> <mfrac> <mrow> <mn>3</mn> <mi>n</mi> </mrow> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo>-</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$n\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.

3-path-connectivity of bubble-sort star graphs

期刊论文
发表日期：

2026年1月3日

查看全文

Yi-Lu Luo,
Yun-Ping Deng,
Yuan Sun

摘要

Let G be a simple connected graph with vertex set V(G) and edge set E(G). Let T be a subset of V(G) with cardinality $|T|\ge 2$ $| T | \geq 2$ . A path connecting all vertices of T is called a T-path of G. Two T-paths $P_i$ $P_{i}$ and $P_j$ $P_{j}$ are $\overline{T}$ $\bar{T}$ -disjoint if $V(P_i)\cap V(P_j)=T$ $V (P_{i}) \cap V (P_{j}) = T$ and $E(P_i)\cap E(P_j)=\emptyset$ $E (P_{i}) \cap E (P_{j}) = \emptyset$ . Denote by $\pi _G(T)$ $π_{G} (T)$ the maximum number of $\overline{T}$ $\bar{T}$ -disjoint paths in G. For an integer $\ell$ $ℓ$ with $\ell \ge 2$ $ℓ \geq 2$ , the $\ell$ $ℓ$ -path-connectivity $\pi _\ell (G)$ $π_{ℓ} (G)$ of G is formulated as $\min \{\pi _G(T)\mid T\subseteq V(G)$ $min {π_{G} (T) ∣ T \subseteq V (G)$ and $|T|=\ell \}$ $| T | = ℓ}$ . In this paper, we study the 3-path-connectivity of the n-dimensional bubble-sort star graph $BS_n$ $B S_{n}$ . As a promising interconnection network topology for high-performance computing (HPC) systems, $BS_n$ $B S_{n}$ possesses numerous superior properties. By deeply analyzing its structural characteristics, we show that $\pi _3(BS_n)=\lfloor \frac{3n}{2}\rfloor -3$ $π_{3} (B S_{n}) = ⌊ \frac{3 n}{2} ⌋ - 3$ for any $n\ge 3$ $n \geq 3$ .