On Computing Component (Edge) Connectivities of Balanced Hypercubes. (4th September 2019)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Chang, Jou-Ming; Hao, Rong-Xia
• Is Part Of: Computer journal. Volume 63:Number 9(2020)
• Page Start: 1311
• Page End: 1320
• Publication Date: 2019-09-04
• Subjects: interconnection networks -- generalized connectivity -- component connectivity -- component edge connectivity -- balanced hypercubes; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz058
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: For an integer $\ell \geqslant 2$, the $\ell $ -component connectivity (resp. $\ell $ -component edge connectivity) of a graph $G$, denoted by $\kappa _{\ell }(G)$ (resp. $\lambda _{\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 $\kappa _{\ell }(BH_n)$ ($\lambda _{\ell }(BH_n)$ ). For $\ell $ -component connectivity, we prove that $\kappa _2(BH_n)=\kappa _3(BH_n)=2n$ for $n\geq 2$, $\kappa _4(BH_n)=\kappa _5(BH_n)=4n-2$ for $n\geq 4$, $\kappa _6(BH_n)=\kappa _7(BH_n)=6n-6$ for $n\geq 5$ . For $\ell $ -component edge connectivity, we prove that $\lambda _3(BH_n)=4n-1$, $\lambda _4(BH_n)=6n-2$ for $n\geq 2$ and $\lambda _5(BH_n)=8n-4$ for $n\geq 3$ . Moreover, we also prove $\lambda _\ell (BH_n)\leq 2n(\ell -1)-2\ell +6$ for $4\leq \ell \leq 2n+3$ and the upper bound of $\lambda _\ell (BH_n)$ we obtained is tight for $\ell =4, 5$ .