Relationship Between Extra Connectivity and Component Connectivity In Networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Xiaoyan LI
  • Cheng-Kuan LIN
  • Jianxi FAN
  • Baolei CHENG
  • Jingya ZHOU

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)38-53
Journal / PublicationComputer Journal
Volume64
Issue number1
Online published15 Feb 2020
Publication statusPublished - Jan 2021

Abstract

Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The h-extra connectivity κh(G) of a graph G is the minimum number of nodes whose removal will disconnect G, and every remaining component has at least h + 1 nodes. Moreover, the h-component connectivity h(G) of G is the minimum number of nodes whose deletion results in a graph with at least h components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well.

Research Area(s)

  • component connectivity, extra connectivity, irregular networks, regular networks, reliability

Citation Format(s)

Relationship Between Extra Connectivity and Component Connectivity In Networks. / LI, Xiaoyan; LIN, Cheng-Kuan; FAN, Jianxi; JIA, Xiaohua; CHENG, Baolei; ZHOU, Jingya.

In: Computer Journal, Vol. 64, No. 1, 01.2021, p. 38-53.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review