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 -