The h-extra connectivity and h-extra conditional diagnosability of Bubble-sort star graphs

Reliability evaluation and fault diagnosis of interconnection networks are important to the design and maintenance of multiprocessor systems. The h-extra connectivity and h-extra conditional diagnosability are important measures for the reliability and fault diagnosis capability of interconnection networks respectively. Due to their many attractive properties, Bubble-sort star graphs have received much research interest recently. In this paper, the minimum h-cluster degree, h-extra connectivity of n-dimensional Bubble-sort star graph (BSn) and h-extra conditional diagnosability of BSn under the PMC model are explored. The following are the main results of this paper: (1) The minimum 2, 3-cluster degree of BSn is determined; (2) The 1, 2-extra connectivity of BSn equals their minimum 2, 3-cluster degree for n >= 4 and n >= 6 respectively; (3) The 1, 2-extra conditional diagnosability of BSn under the PMC model equals their 1, 2-extra connectivity plus h for n >= 4 and n >= 6 respectively; (4) An algorithm for determining the h-extra connectivity of general simple graphs is also constructed in this paper and it is used to determine the h-extra connectivity of Bubble-sort star graphs of low dimensions. (C) 2018 Published by Elsevier B.V.