The Structure connectivity of Enhanced Hypercube Networks

Abstract

The n-dimensional enhanced hypercube $Q_{n,k}(1\le k\le n-1)$ is one of the most attractive interconnection networks for parallel and distributed computing system. Let $H$ be a certain particular connected subgraph of graph $G$. The $H$-structure-connectivity of $G$, denoted by $\kappa (G;H),$ is the cardinality of minimal set of subgraphs $F=\{H_1,H_2,\dots ,H_m\}$ in $G$ such that every $H_i\in F$ is isomprphic to $H$ and $G-F$ is disconnected. The $H$-substructure-connectivity of $G$, denoted by ${}_k^3(G;H)$, is the cardinality of minimal set of subgraphs $F=H_1,H_2,\dots ,H_m$ in $G$ such that every $H_i\in F$ is isomorphic to a connected subgraph $H$ , and $G-F$ is disconnected. Using the structural properties of $Q_{n,k}$ the $H$-structure-connectivity $\kappa (Q_{n,k};H)$ were determine for $H\in \{K_1,K_{1,1},K_{1,2},K_{1,3}\}$.