On Computing Component (Edge) Connectivities of Balanced Hypercubes. (4th September 2019) - Gu, Mei-Mei; Chang, Jou-Ming; Hao, Rong-Xia
Abstract: For an integer 2, the -component connectivity (resp. -component edge connectivity) of a graph G, denoted by κ _(G) (resp. λ _(G) ), is the minimum number of vertices (resp. edges) whose removal from G results in a disconnected graph with at least 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 -component (edge) connectivity κ _(BH_n) (λ _(BH_n) ). For -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 -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 λ _(BH_n)≤ 2n(-1)-2+6 for 4≤ ≤ 2n+3 and the upper bound of λ _(BH_n) we obtained is tight for =4, 5 .