On Computing Component (Edge) Connectivities of Balanced Hypercubes. (4th September 2019) - Gu, Mei-Mei; Chang, Jou-Ming; Hao, Rong-Xia
Abstract: For an integer $\ell \geqslant 2$, the $\ell $ -component connectivity (resp. $\ell $ -component edge connectivity) of a graph $G$, denoted by $κ _{\ell }(G)$ (resp. $λ _{\ell }(G)$ ), is the minimum number of vertices (resp. edges) whose removal from $G$ results in a disconnected graph with at least $\ell $ components. The two parameters naturally generalize the classical connectivity and edge connectivity of graphs defined in term of the minimum vertex-cut and the minimum edge-cut, respectively. The two kinds of connectivities can help us to measure the robustness of the graph corresponding to a network. In this paper, by exploring algebraic and combinatorial properties of $n$ -dimensional balanced hypercubes $BH_n$, we obtain the $\ell $ -component (edge) connectivity $κ _{\ell }(BH_n)$ ($λ _{\ell }(BH_n)$ ). For $\ell $ -component connectivity, we prove that $κ _2(BH_n)=κ _3(BH_n)=2n$ for $n≥ 2$, $κ _4(BH_n)=κ _5(BH_n)=4n-2$ for $n≥ 4$, $κ _6(BH_n)=κ _7(BH_n)=6n-6$ for $n≥ 5$ . For $\ell $ -component edge connectivity, we prove that $λ _3(BH_n)=4n-1$, $λ _4(BH_n)=6n-2$ for $n≥ 2$ and $λ _5(BH_n)=8n-4$ for $n≥ 3$ . Moreover, we also prove $λ _\ell (BH_n)≤ 2n(\ell -1)-2\ell +6$ for $4≤ \ell ≤ 2n+3$ and the upper bound of $λ _\ell (BH_n)$ we obtained is tight for $\ell =4, 5$ .