Let G be a simple connected graph with vertex set V(G). For S ⊆ V(G), let πG(S) denote the maximum cardinality of internally disjoint S-paths in G. For an integer k with k ≥ 2, the k-path-connectivity πk(G) is defined as the minimum πG(S) over all k-subsets S of V(G). It is proved that deciding whether πG(S) ≥ r is NP-complete problem [Graphs Combin. 37 (2021) 2521–2533]. The hypercube Qn is the famous Cayley graph, which is widely studied in the research of developing multiprocessor systems. The hierarchical cubic network HCNn is given in [IEEE TPDS 6 (1995) 427–435] which takes Qn as building clusters and emulates the desirable properties very efficiently. In this paper, we consider the 3-path-connectivity of HCNn and prove that <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\pi_{3}(HCN_{n})=\lfloor {3n+2 \over 4}\rfloor$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mi>π</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>H</mi> <mi>C</mi> <msub> <mi>N</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mo fence="false" stretchy="false">⌊</mo> <mrow> <mfrac> <mrow> <mn>3</mn> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> <mn>4</mn> </mfrac> </mrow> <mo fence="false" stretchy="false">⌋</mo> </math></EquationSource> </InlineEquation> by constructing multiple internally disjoint S-paths. This result improves the 3-tree-connectivity [Discrete Appl. Math. 322 (2022) 203–209] from trees to paths.

The Path-Connectivity of Hierarchical Cubic Networks

期刊论文
发表日期：

2026年1月2日

查看全文

Ruo-xuan Li,
Rong-xia Hao,
Zhen He,
Young Soo Kwon

摘要

Let G be a simple connected graph with vertex set V(G). For S ⊆ V(G), let π_G(S) denote the maximum cardinality of internally disjoint S-paths in G. For an integer k with k ≥ 2, the k-path-connectivity π_k(G) is defined as the minimum π_G(S) over all k-subsets S of V(G). It is proved that deciding whether π_G(S) ≥ r is NP-complete problem [Graphs Combin. 37 (2021) 2521–2533]. The hypercube Q_n is the famous Cayley graph, which is widely studied in the research of developing multiprocessor systems. The hierarchical cubic network HCN_n is given in [IEEE TPDS 6 (1995) 427–435] which takes Q_n as building clusters and emulates the desirable properties very efficiently. In this paper, we consider the 3-path-connectivity of HCN_n and prove that $\pi_{3}(HCN_{n})=\lfloor {3n+2 \over 4}\rfloor$ $π_{3} (H C N_{n}) = ⌊ \frac{3 n + 2}{4} ⌋$ by constructing multiple internally disjoint S-paths. This result improves the 3-tree-connectivity [Discrete Appl. Math. 322 (2022) 203–209] from trees to paths.