A new approach to finding the extra connectivity of graphs

The connectivity of a graph is the minimum number of nodes, whose removal will cause the graph disconnected. It is one of the basic and important properties of the graph, and can be used as a metric of the graph's robustness. Since the connectivity of a graph is upper-bounded by its minimal node-degree, which can be small, the notion of conditional connectivity has been proposed in the past to more realistically reflect a graph's robustness. The extra connectivity is such a conditional connectivity. In this paper, we introduce a new approach to finding the extra connectivity of the hypercube, a well-known regular graph model for networks of parallel computers. We will show that the results on the isoperimetric inequalities for hypercubes can be used to obtain their extra connectivity. That is, using isoperimetric inequalities, for an n-dimensional hypercube Q_n with n≥5, the h-extra connectivity is equal to its minimum (h+1)-vertex boundary number for 1≤h≤n−4 and n+1≤h≤2n−4. For n−3≤h≤n, the h-extra connectivity of hypercube equals its minimum (n−2)-vertex boundary number. The paper's result for the first time establishes a relationship between the isoperimetric inequalities and the extra connectivity of graphs.