Embedded connectivity of recursive networks

Abstract

Let $G_n$ be an $n$-dimensional recursive network. The $h$-embedded connectivity ${\zeta }_h(G_n)$ (resp. edge-connectivity ${\eta }_h(G_n)$) of $G_n$ is the minimum number of vertices (resp. edges) whose removal results in disconnected and each vertex is contained in an $h$-dimensional subnetwork $G_h$. This paper determines ${\zeta }_h$ and ${\eta }_h$ for the hypercube $Q_n$ and the star graph $S_n$, and ${\eta }_3$ for the bubble-sort network $B_n$.