A new approach to finding the extra connectivity of graphs

Qiang Zhu, Fang Ma, Guodong Guo, Dajin Wang

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)265-271
Number of pages7
JournalDiscrete Applied Mathematics
Volume294
DOIs
StatePublished - 15 May 2021

Keywords

  • Connectivity
  • Extra connectivity
  • Hypercubes
  • Isoperimetric properties for graphs
  • Networks
  • Reliability

Fingerprint Dive into the research topics of 'A new approach to finding the extra connectivity of graphs'. Together they form a unique fingerprint.

Cite this