TY - JOUR
T1 - A new approach to finding the extra connectivity of graphs
AU - Zhu, Qiang
AU - Ma, Fang
AU - Guo, Guodong
AU - Wang, Dajin
N1 - Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/5/15
Y1 - 2021/5/15
N2 - 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 Qn 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.
AB - 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 Qn 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.
KW - Connectivity
KW - Extra connectivity
KW - Hypercubes
KW - Isoperimetric properties for graphs
KW - Networks
KW - Reliability
UR - http://www.scopus.com/inward/record.url?scp=85101550812&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2021.02.017
DO - 10.1016/j.dam.2021.02.017
M3 - Article
AN - SCOPUS:85101550812
SN - 0166-218X
VL - 294
SP - 265
EP - 271
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -