Fault-tolerability analysis of hierarchical pancake networks based on 1-extra 3-component connectivity
Abstract
The topology of interconnection networks is fundamental to the performance and reliability of parallel and distributed systems. Typically, an interconnection network is modeled as a graph, and connectivity of a graph serves as a critical parameter for measuring network reliability. The $h$-extra $r$-component vertex (resp. edge) connectivity of a graph~$G$, denoted by $c\kappa_{r}^{h}(G)$ (resp. $c\lambda_{r}^{h}(G)$), is the minimum number of vertices (resp. edges) whose removal results in a disconnected graph with at least $r$ components, in which each component contains at least $h+1$ vertices. In this paper, we investigate the hierarchical pancake network~$\mathcal{HP}_n$, a highly symmetric and recursively structured Cayley-type topology, and show that $c\kappa^1_3(\mathcal{HP}_n) = 4n - 6$ and $c\lambda^1_3(\mathcal{HP}_n) = 4n - 6$ for $n \ge 4$.