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. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

Connectivity of a graph refers to the minimum number of nodes whose removal will disconnect the graph, serving as a metric of the graph's robustness. Conditional connectivity has been proposed to more realistically reflect a graph's robustness, with extra connectivity being a form of this concept. This paper introduces a new approach to find the extra connectivity of hypercubes and establishes a relationship between isoperimetric inequalities and the extra connectivity of graphs.