On Computing Component (Edge) Connectivities of Balanced Hypercubes

For an integer , the -component connectivity (resp. -component edge connectivity) of a graph , denoted by (resp. ), is the minimum number of vertices (resp. edges) whose removal from 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 -dimensional balanced hypercubes , we obtain the -component (edge) connectivity (). For -component connectivity, we prove that for , for , for . For -component edge connectivity, we prove that , for and for . Moreover, we also prove for and the upper bound of we obtained is tight for .