TITLE:
The Generalized 4-Connectivity of Hierarchical Pancake Graphs
AUTHORS:
Qingwen Zhang
KEYWORDS:
Generalized k-Connectivity, Pancake Graphs, Hierarchical Pancake Graphs, Interconnection Networks
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.14 No.11,
November
11,
2026
ABSTRACT: The generalized
k
-connectivity
κ
k
(
G
)
of a graph
G
is a parameter that measures the reliability and fault tolerance of networks, generalizing the classical connectivity
κ(
G
)
in the sense that
κ
2
(
G
)=κ(
G
)
. The hierarchical pancake graph
H
P
n
is an important interconnection topology constructed by taking pancake graphs as its building blocks. In this paper, we investigate the generalized 4-connectivity of
H
P
n
and show that
κ
4
(
H
P
n
)=n−1
for
n≥3
. That is, for any 4-vertex subset
S⊆V(
H
P
n
)
, there exist at least
n−1
internally disjoint
S
-trees in
H
P
n
.