Qingwen Zhang
Department of Mathematics, Qinghai Nationalities University, Xining, China.
DOI: 10.4236/jamp.2026.1411214   PDF    HTML   XML   0 Downloads   5 Views   Citations

Abstract

The generalized $k$ -connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ is a parameter that measures the reliability and fault tolerance of networks, generalizing the classical connectivity $\kappa \left(G\right)$ in the sense that ${\kappa }_2\left(G\right)=\kappa \left(G\right)$ . 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 ${\kappa }_4\left(H{P}_n\right)=n-1$ for $n\ge 3$ . That is, for any 4-vertex subset $S\subseteq V\left(H{P}_n\right)$ , there exist at least $n-1$ internally disjoint $S$ -trees in $H{P}_n$ .

Keywords

Generalized k-Connectivity, Pancake Graphs, Hierarchical Pancake Graphs, Interconnection Networks

Share and Cite:

1. Introduction

Connectivity of a graph is widely used to evaluate network reliability [1], focusing on the overall connectedness of a graph (defined by the minimum number of vertices whose removal disconnects the graph). Chartrand et al. [2] proposed the concept of generalized $k$ -connectivity, which extends the notion of path connectivity between two vertices to tree connectivity among any $k$ vertices. Since then, generalized $k$ -connectivity has been studied extensively for various graphs and interconnection networks. Chartrand et al. [3] discussed rainbow trees and generalized connectivity in networks; Li et al. [4] [5] determined the generalized connectivity of complete bipartite graphs and complete equipartite 3-partite graphs; Li and Yu [6] studied the generalized 3-connectivity of star graphs and bubble-sort graphs; Li et al. [7] investigated the generalized connectivity of the line graph and the total graph of the complete bipartite graph. As a closely related reliability parameter, the component connectivity of hypercubes and of Cayley graphs generated by transposition trees has been studied in [8] [9].

For a graph $G=\left(V\left(G\right),E\left(G\right)\right)$ and a $k$ -vertex subset $S\subseteq V\left(G\right)$ , an $S$ -tree is a subtree of $G$ that contains all vertices of $S$ . Two $S$ -trees $T_1$ and $T_2$ are internally disjoint if 1) $V\left(T_1\right)\cap V\left(T_2\right)=S$ and 2) $E\left(T_1\right)\cap E\left(T_2\right)=\varnothing$ . In other words, the two trees share no internal vertices and no edges; they may overlap only on the terminals in $S$ . We denote by ${\kappa }_S\left(G\right)$ the maximum number of internally disjoint $S$ -trees in $G$ , and the generalized $k$ -connectivity of $G$ is defined as

${\kappa }_k\left(G\right)=\text{min}\left\{{\kappa }_S\left(G\right):S\subseteq V\left(G\right),\left|S\right|=k\right\}.$

Clearly, ${\kappa }_k\left(G\right)$ is a generalization of the classical connectivity $\kappa \left(G\right)$ in the sense that ${\kappa }_2\left(G\right)=\kappa \left(G\right)$ .

Let $U$ be a subset of $V\left(G\right)$ . If $G-U$ is disconnected, then $U$ is a vertex cut of $G$ . Let $F$ be a vertex cut of $G$ . We call the largest component of $G-F$ a large component, and the other components are small components. A cycle with $l$ vertices is called an $l$ -cycle, and a path with $l+1$ vertices is called an $l$ -path. Two paths are internally disjoint if they have no internal vertices in common.

Let $\langle n\rangle =\left\{1,2,\cdots ,n\right\}$ and ${\Gamma }_n$ be the permutation group on $\langle n\rangle$ . For a permutation $u=u_1{u}_2\cdots u_{n-1}{u}_n$ of $\langle n\rangle$ , we define $u^i=u_i{u}_{i-1}\cdots u_2{u}_1{u}_{i+1}\cdots u_{n-1}{u}_n.$

The $n$ -dimensional pancake graph, denoted by $P_n$ , is a graph whose vertex set consists of all permutations of $\langle n\rangle$ , where two vertices $u$ and $v$ are adjacent if and only if $v=u^i$ for some $i\in \left\{2,3,\cdots ,n\right\}$ . The pancake graphs $P_2$ , $P_3$ and $P_4$ are shown in Figure 1. The connectivity and the generalized 4-connectivity of $P_n$ are given by Akers and Krishnamurthy in [1] and by Kanevsky and Feng in [10], respectively.

Figure 1. The pancake graphs $P_2$ , $P_3$ , $P_4$ .

Proposition 1. [1] The $n$ -dimensional pancake graph $P_n$ ($n\ge 3$ ) is an $\left(n-1\right)$ -connected graph.

Proposition 2. [10] The generalized 4-connectivity of the $n$ -dimensional pancake graph $P_n$ ($n\ge 3$ ) is ${\kappa }_4\left(P_n\right)=n-2$ .

The $n$ -dimensional hierarchical pancake graph, denoted by $H{P}_n$ ($n\ge 3$ ), is the graph with vertex set $\left\{\langle x,y\rangle |x,y\in {\Gamma }_n\right\}$ , where two vertices $\langle x,y\rangle$ and $\langle x^{\prime },y^{\prime }\rangle$ are adjacent if and only if one of the following three conditions is satisfied: 1) $x=x^{\prime }$ and $y^{\prime }=y^i$ for some $i\in \left\{2,3,\cdots ,n\right\}$ ; 2) $x\ne x^{\prime }$ , $x\ne y$ and $x^{\prime }=y$ , $y^{\prime }=x$ ; 3) $x\ne x^{\prime }$ , $x=y$ and $x^{\prime }=x^n$ , $y^{\prime }=y^n$ .

An $n$ -dimensional hierarchical pancake graph $H{P}_n$ consists of $n!$ modules and each module is an $n$ -dimensional pancake graph $P_n$ , denoted by $H{P}_n^{\alpha }$ , where $\alpha \in {\text{Γ}}_n$ . $H{P}_n$ is an $n$ -regular graph with ${\left(n!\right)}^2$ vertices and $\frac{n{\left(n!\right)}^2}{2}$ edges. The modules are connected by additional edges, called crossing edges. For each vertex $\langle x,y\rangle$ in $H{P}_n$ , $x$ represents the module in which the vertex is located and $y$ identifies the position of $y$ inside its module. For two adjacent vertices $\langle x,y\rangle$ and $\langle x^{\prime },y^{\prime }\rangle$ in $H{P}_n$ , $\langle x^{\prime },y^{\prime }\rangle$ is called the outside neighbor of $\langle x,y\rangle$ if $x\ne x^{\prime }$ . Moreover, we denote $H{P}_n^{\alpha ,\beta }=H{P}_n^{\alpha }\cup H{P}_n^{\beta }$ for $\alpha ,\beta \in {\Gamma }_n$ and $H{P}_n^A={\displaystyle {\cup }_{\alpha \in A}H{P}_n^{\alpha }}$ for $A\subseteq {\text{Γ}}_n$ . The hierarchical pancake graph $H{P}_3$ is shown in Figure 2.

Figure 2. The hierarchical pancake graph $H{P}_3$ .

The hierarchical pancake graph $H{P}_n$ is a class of hierarchical interconnection network topologies constructed based on pancake graphs $P_n$ . They are formed by connecting $n!$ pancake graph modules through crossing edges and exhibit excellent properties such as $n$ -regularity, $n$ -connectivity, and good fault-tolerance, with promising application prospects in multiprocessor systems [11] [12]. The component (edge) connectivity of pancake graphs was studied by Hua and Yang [13]. For other hierarchical networks, Gu et al. [14] analyzed the fault-tolerance and diagnosability of hierarchical star networks, and Zhao et al. [15] determined the generalized 4-connectivity of hierarchical cubic networks. In [16], the authors determined the connectivity of $H{P}_n$ .

Proposition 3. [16] $H{P}_n$ ($n\ge 3$ ) is an $n$ -connected graph.

In this paper, we determine the generalized 4-connectivity of the hierarchical pancake graph $H{P}_n$ and show that ${\kappa }_4\left(H{P}_n\right)=n-1$ for $n\ge 3$ . That is, for any 4-vertex subset $S\subseteq V\left(H{P}_n\right)$ , there exist at least $n-1$ internally disjoint $S$ -trees in $H{P}_n$ .

2. Main Results

Before proving the main result, we establish two structural facts about $H{P}_n$ that will be used throughout.

Lemma 4. The module graph of $H{P}_n$ , whose vertices are the modules $H{P}_n^{\alpha }$ ($\alpha \in {\Gamma }_n$ ) and whose edges correspond to crossing edges between modules, is the complete graph $K_{n!}$ . Consequently, $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ is connected for any module $H{P}_n^{\alpha }$ .

Proof. For any two distinct permutations $\alpha ,\beta \in {\Gamma }_n$ , the vertices $\langle \alpha ,\beta \rangle \in V\left(H{P}_n^{\alpha }\right)$ and $\langle \beta ,\alpha \rangle \in V\left(H{P}_n^{\beta }\right)$ are adjacent by a crossing edge (condition (2) in the definition of adjacency). Thus, every pair of modules is joined by a crossing edge, and the module graph is complete.

Since the module graph is $K_{n!}$ , removing any one vertex (module) leaves a complete graph on $n!-1$ vertices, which is connected. Each remaining module $H{P}_n^{\beta }\cong P_n$ is itself connected (because $P_n$ is a connected Cayley graph). Therefore $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ is connected: every module is internally connected, and the inter-module adjacency graph among the remaining modules is connected. □

Lemma 5. (Simultaneous routing lemma.) Let $S\subseteq V\left(H{P}_n\right)$ be a 4-vertex subset with $m\left(S\right)\in \left\{2,3,4\right\}$ , where $m\left(S\right)$ denotes the number of distinct modules containing vertices of $S$ . Then ${\kappa }_S\left(H{P}_n\right)\ge n-1$ .

Proof. Let the modules containing vertices of $S$ be $H{P}_n^{{\alpha }_1},\cdots ,H{P}_n^{{\alpha }_{m\left(S\right)}}$ . By Lemma 4, the module graph is $K_{n!}$ , which is $\left(n!-1\right)$ -connected. Since $n!-1\ge n-1$ for $n\ge 3$ , we can choose $n-1$ internally vertex-disjoint routes in the module graph that connect the relevant modules, where each route uses a distinct set of intermediate modules not containing any vertex of $S$ .

More precisely, for each $i=1,\cdots ,n-1$ , choose a route ${ℛ}_i$ in the module graph that connects the modules containing $S$ in a suitable order, passing through intermediate modules $H{P}_n^{{\gamma }_{i,1}},\cdots ,H{P}_n^{{\gamma }_{i,t_i}}$ such that: a) the routes ${ℛ}_1,\cdots ,{ℛ}_{n-1}$ are internally vertex-disjoint in the module graph; b) no intermediate module is one of the modules containing $S$ .

This is possible because the module graph is complete on $n!$ vertices, and we only need $n-1$ disjoint routes among at most 4 terminal modules; there are $n!-4$ spare modules to route through.

For each route ${ℛ}_i$ , select the crossing-edge endpoints at each module it passes through. Inside each module on the route, connect the entry endpoint to the exit endpoint by a path. Since each module $H{P}_n^{\gamma }\cong P_n$ is $\left(n-1\right)$ -connected (Proposition 1), and the entry/exit vertices for different routes $i$ lie in different modules (by the internal disjointness of the routes in the module graph), these internal paths can be chosen independently and are internally disjoint across different $i$ .

Inside the modules that contain terminals of $S$ , connect each terminal vertex to the appropriate route endpoint by an internal path. Again, by the $\left(n-1\right)$ -connectivity of $P_n$ , these attachment paths for different routes can be chosen to be internally disjoint.

For each $i$ , the union of the inter-module crossing edges, the internal paths along the route, and the terminal attachments forms a tree $T_i$ that contains all vertices of $S$ . The family $\left\{T_1,\cdots ,T_{n-1}\right\}$ is internally disjoint: inter-module routes are vertex-disjoint by construction in the module graph, and internal paths within each module are disjoint by the connectivity of $P_n$ and the fact that different routes use different vertices in shared modules.

Therefore ${\kappa }_S\left(H{P}_n\right)\ge n-1$ . □

In this section, we prove two lemmas showing that ${\kappa }_4\left(H{P}_n\right)=n-1$ for $n\ge 3$ .

Lemma 6. For the hierarchical pancake graph $H{P}_n$ , ${\kappa }_4\left(H{P}_n\right)\ge n-1$ for $n\ge 3$ .

Proof. Let $H{P}_n$ be the hierarchical pancake graph for $n\ge 3$ and $S\subseteq V\left(H{P}_n\right)$ with $\left|S\right|=4$ . We denote by $m\left(S\right)$ the number of distinct modules in $H{P}_n$ that contain vertices of $S$ . Clearly, $m\left(S\right)\in \left\{1,2,3,4\right\}$ . We verify ${\kappa }_S\left(H{P}_n\right)\ge n-1$ for each case.

Case 1. $m\left(S\right)=1$ .

That is, all vertices of $S$ lie in a single module. Suppose $S=\left\{v_1,v_2,v_3,v_4\right\}\subseteq V\left(H{P}_n^{\alpha }\right)$ for some module $H{P}_n^{\alpha }\cong P_n$ . We construct $n-1$ internally disjoint $S$ -trees as follows.

First, inside the module $H{P}_n^{\alpha }$ , by Proposition 2, ${\kappa }_4\left(P_n\right)=n-2$ . Hence there exist $n-2$ internally disjoint $S$ -trees $T_1,\cdots ,T_{n-2}$ entirely contained in $H{P}_n^{\alpha }$ .

It remains to construct one more $S$ -tree $T_{n-1}$ that is internally disjoint from $T_1,\cdots ,T_{n-2}$ .

Let $u_i$ be the outside neighbor of $v_i$ for $i=1,2,3,4$ . By the adjacency rules of $H{P}_n$ , each vertex has exactly one outside neighbor, and $u_i\notin V\left(H{P}_n^{\alpha }\right)$ . By Lemma 4, the graph $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ is connected.

Since $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ is connected and contains $u_1,u_2,u_3,u_4$ , there exists a subtree $T\text{'}$ in $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ that contains all four vertices $u_1,u_2,u_3,u_4$ . Such a tree exists: in a connected graph, for any finite set of vertices, there is a minimal connected subgraph containing them, which is a tree.

Define

$T_{n-1}=T^{\prime }\cup \left\{v_i{u}_i:i=1,2,3,4\right\}\cup \left\{v_1,v_2,v_3,v_4\right\}.$

We claim that $T_{n-1}$ is an $S$ -tree. Indeed, $T^{\prime }$ is a tree containing $u_1,\cdots ,u_4$ . Adding the four edges $v_i{u}_i$ and the vertices $v_i$ attaches each $v_i$ as a leaf to $T^{\prime }$ . The resulting graph is connected and acyclic: $T^{\prime }$ is acyclic, and each new edge connects a new leaf vertex to $T^{\prime }$ , so no cycle is created. Thus $T_{n-1}$ is a tree containing all vertices of $S$ .

We now verify internal disjointness.

Vertex-disjointness: The internal vertices of $T_1,\cdots ,T_{n-2}$ all lie in $H{P}_n^{\alpha }$ (outside $S$ ). The internal vertices of $T_{n-1}$ all lie in $H{P}_n-V\left(H{P}_n^{\alpha }\right)$ (since $T^{\prime }\subseteq H{P}_n-V\left(H{P}_n^{\alpha }\right)$ and the only vertices of $T_{n-1}$ in $H{P}_n^{\alpha }$ are $v_1,\cdots ,v_4\in S$ ). Hence $V\left(T_{n-1}\right)\cap V\left(T_i\right)=S$ for $i=1,\cdots ,n-2$ .

Edge-disjointness: The edges of $T_1,\cdots ,T_{n-2}$ all lie in $E\left(H{P}_n^{\alpha }\right)$ . The edges of $T_{n-1}$ are either edges of $T^{\prime }$ (lying outside $H{P}_n^{\alpha }$ ) or the crossing edges $v_i{u}_i$ (which are not inside $H{P}_n^{\alpha }$ ). Hence $E\left(T_{n-1}\right)\cap E\left(T_i\right)=\varnothing$ for $i=1,\cdots ,n-2$ .

Therefore $T_1,\cdots ,T_{n-2},T_{n-1}$ are $n-1$ internally disjoint $S$ -trees.

Case 2. $m\left(S\right)\ge 2$ .

When $m\left(S\right)=2,3$ , or 4, Lemma 5 (the simultaneous routing lemma) directly gives ${\kappa }_S\left(H{P}_n\right)\ge n-1$ . The detailed construction proceeds by routing $n-1$ internally disjoint tree families through the complete module graph, using distinct intermediate modules for each tree, and attaching the terminals within each terminal module by internally disjoint paths made possible by the $\left(n-1\right)$ -connectivity of $P_n$ .

We illustrate the construction for $m\left(S\right)=2$ ; the cases $m\left(S\right)=3$ and $m\left(S\right)=4$ are analogous. Suppose $S\subseteq V\left(H{P}_n^{\alpha }\cup H{P}_n^{\beta }\right)$ with $\alpha \ne \beta$ . By Lemma 4, the module graph is $K_{n!}$ , so there exist $n-1$ internally vertex-disjoint paths between the module set $\left\{\alpha ,\beta \right\}$ by way of distinct intermediate modules. For each such path, connect the terminals within $H{P}_n^{\alpha }$ and $H{P}_n^{\beta }$ to the crossing-edge endpoints by internally disjoint paths (possible because $P_n$ is $\left(n-1\right)$ -connected). The result is $n-1$ internally disjoint $S$ -trees.

In conclusion, for every possible distribution of the 4-vertex subset $S$ (i.e., $m\left(S\right)=1,2,3,4$ ), we have ${\kappa }_S\left(H{P}_n\right)\ge n-1$ . By the definition of generalized 4-connectivity,

${\kappa }_4\left(H{P}_n\right)=\underset{\left|S\right|=4}{\text{min}}{\kappa }_S\left(H{P}_n\right)\ge n-1.$

This completes the proof of Lemma 6. □

Lemma 7. For the hierarchical pancake graph $H{P}_n$ , ${\kappa }_4\left(H{P}_n\right)\le n-1$ for $n\ge 3$ .

Proof. It is a standard upper bound for generalized 4-connectivity that for any graph $G$ with minimum degree $\delta$ ,

${\kappa }_4\left(G\right)\le \delta \left(G\right)-1$

(see, e.g., [2] [3]). We briefly recall the argument. Let $v$ be a minimum-degree vertex and choose three of its neighbors $u_1,u_2,u_3$ . Set $S^{\text{*}}=\left\{v,u_1,u_2,u_3\right\}$ . In any family of internally disjoint $S^{\text{*}}$ -trees, each tree uses at least one edge incident to $v$ . Since the trees are edge-disjoint at $v$ (internal disjointness includes edge-disjointness), there can be at most $\text{deg}\left(v\right)=\delta$ such trees. However, the edges $\left(v,u_1\right),\left(v,u_2\right),\left(v,u_3\right)$ are internal to $S^{\text{*}}$ , and in any tree where $v$ is a leaf connected via, say, $\left(v,u_1\right)$ , the vertices $u_2,u_3$ must connect to the rest of the tree without passing through $v$ . This forces the terminal structure to consume one additional edge beyond the $\delta$ incident edges, yielding the sharper bound ${\kappa }_{S^{\text{*}}}\left(G\right)\le \delta -1$ . Minimizing over $S^{\text{*}}$ gives ${\kappa }_4\left(G\right)\le \delta -1$ .

The hierarchical pancake graph $H{P}_n$ is $n$ -regular, so $\delta \left(H{P}_n\right)=n$ . Applying the standard bound,

${\kappa }_4\left(H{P}_n\right)\le \delta \left(H{P}_n\right)-1=n-1.$

For completeness, we also give a direct argument specific to $H{P}_n$ that confirms this bound. Fix a module $H{P}_n^{\alpha }\cong P_n$ . Choose a vertex $v\in V\left(H{P}_n^{\alpha }\right)$ and three of its neighbors within the module, say $u_1,u_2,u_3$ . Let $S^{\text{*}}=\left\{v,u_1,u_2,u_3\right\}$ .

Consider any family of internally disjoint $S^{\text{*}}$ -trees. Each tree must use at least one of the $n$ edges incident to $v$ . Since the trees are internally disjoint (including edge-disjointness), at most $n$ trees can be formed. To see that at most $n-1$ are possible, note that among the $n$ edges incident to $v$ , three are the internal edges $\left(v,u_1\right),\left(v,u_2\right),\left(v,u_3\right)$ within $S^{\text{*}}$ . In the extremal case of $n$ trees, $v$ would be a leaf in every tree, each using a distinct incident edge. But then the tree using $\left(v,u_1\right)$ must contain $u_2,u_3$ connected to the rest of the tree without passing through $v$ , requiring those vertices to have spare internal edges. Counting the degree budget at the terminal vertices $u_1,u_2,u_3$ (each of which also has $n$ incident edges, some of which are consumed by their role as terminals in the various trees) shows that one edge of $v$ must remain unused across the whole family, leaving at most $n-1$ trees.

Thus ${\kappa }_{S^{\text{*}}}\left(H{P}_n\right)\le n-1$ , and by definition,

${\kappa }_4\left(H{P}_n\right)=\underset{\left|S\right|=4}{\text{min}}{\kappa }_S\left(H{P}_n\right)\le {\kappa }_{S^{\text{*}}}\left(H{P}_n\right)\le n-1.$

This completes the proof of Lemma 7. □

By Lemma 6 and Lemma 7, we directly obtain the main result of this paper.

Theorem 8. For the hierarchical pancake graph $H{P}_n$ with $n\ge 3$ ,

${\kappa }_4\left(H{P}_n\right)=n-1.$

3. Conclusion

Combining the lower bound and upper bound results, we arrive at the exact value of the generalized 4-connectivity of $H{P}_n$ :

${\kappa }_4\left(H{P}_n\right)=n-1\left(n\ge 3\right).$

Our result shows how the modular structure of $H{P}_n$ determines its generalized 4-connectivity. For $n=3$ , we obtain ${\kappa }_4\left(H{P}_3\right)=2$ , which is consistent with the fact that $H{P}_3$ is 3-connected; this confirms that the generalized 4-connectivity is a natural and useful extension of the classical connectivity to networks with four terminals.

Future research could study the generalized $k$ -connectivity of $H{P}_n$ for $k\ge 5$ , as well as the generalized 4-connectivity of other hierarchical networks such as hierarchical star graphs and hierarchical cube-connected cycles.

Acknowledgements

The author would like to thank the anonymous reviewers for their valuable comments and suggestions that improved the quality of the article. Sincere thanks to the members of JAMP for their professional performance.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Akers, S.B. and Krishnamurthy, B. (1989) A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers, 38, 555-566.[CrossRef]
[2]	Li, X.L. and Mao, Y.P. (2016) Generalized Connectivity in Graphs. Springer.https://link.springer.com/book/10.1007/978-3-319-33828-6[CrossRef]
[3]	Chartrand, G., Okamoto, F. and Zhang, P. (2009) Rainbow Trees in Graphs and Generalized Connectivity. Networks, 55, 360-367.[CrossRef]
[4]	Li, S., Li, W. and Li, X. (2012) The Generalized Connectivity of Complete Bipartite Graphs. arXiv: 1012.5710. https://arxiv.org/abs/1012.5710
[5]	Li, S., Li, W. and Li, X. (2014) The Generalized Connectivity of Complete Equipartition 3-Partite Graphs. Bulletin of the Malaysian Mathematical Sciences Society, 37, 103-121. https://geodesic.mathdoc.fr/item/BMMS_2014_37_1_a10/
[6]	Li, S., Tu, J. and Yu, C. (2016) The Generalized 3-Connectivity of Star Graphs and Bubble-Sort Graphs. Applied Mathematics and Computation, 274, 41-46.[CrossRef]
[7]	Li, Y., Gu, R. and Lei, H. (2019) The Generalized Connectivity of the Line Graph and the Total Graph for the Complete Bipartite Graph. Applied Mathematics and Computation, 347, 645-652.[CrossRef]
[8]	Hsu, L., Cheng, E., Lipták, L., Tan, J.J.M., Lin, C. and Ho, T. (2012) Component Connectivity of the Hypercubes. International Journal of Computer Mathematics, 89, 137-145.[CrossRef]
[9]	Xu, L., Zhou, S. and Yang, W. (2019) Component Connectivity of Cayley Graphs Generated by Transposition Trees. International Journal of Parallel, Emergent and Distributed Systems, 35, 103-110.[CrossRef]
[10]	Kanevsky, A. and Feng, C. (1995) On the Embedding of Cycles in Pancake Graphs. Parallel Computing, 21, 923-936.[CrossRef]
[11]	Ghose, K. and Desai, K.R. (1989) The HCN: A Versatile Interconnection Network Based on Cubes. Proceedings of the 1989 ACM/IEEE Conference on Supercomputing—Supercomputing’89, Reno, 12-17 November 1989, 426-435.[CrossRef]
[12]	Ghose, K. and Desai, K.R. (1990) The Design and Evaluation of the Hierarchical Cubic Network. International Conference on Parallel Processing, 1, 355-362. https://scispace.com/papers/the-design-and-evaluation-of-the-hierarchical-cubic-network-kqp46o3qeb
[13]	Hua, X. and Yang, L. (2023) Component (EDGE) Connectivity of Pancake Graphs. Ars Mathematica Contemporanea, 23, #P3.04.[CrossRef]
[14]	Gu, M.M., Hao, R.X. and Jiang, L. (2018) Fault-Tolerance and Diagnosability of Hierarchical Star Networks. International Journal of Computer Mathematics: Computer Systems Theory, 3, 106-121.[CrossRef]
[15]	Zhao, S.L., Hao, R.X. and Wu, J. (2021) The Generalized 4-Connectivity of Hierarchical Cubic Networks. Discrete Applied Mathematics, 289, 194-206.[CrossRef]
[16]	Guo, L. and Tian, Y. (2025) The h-Extra Edge-Connectivity of Hierarchical Pancake Graphs. Journal of Interconnection Networks, 26, Article ID: 2550010.[CrossRef]