Super Connectivity and Diagnosability of Crossed Cubes

Abstract

A multiprocessor system and an interconnection network have a underlying topology, which usually presented by a graph G . In 2016, Zhang et al. proposed the g -extra diagnosability of G, which restrains that every component of G − S has at least ( g +1)  vertices. As an important variant of the hypercube, the n -dimensional crossed cube CQ_n has many good properties. In this paper, we prove that CQ_n is tightly (4n-9) super 3-extra connected for n ≥ 7 and the 3-extra diagnosability of CQ_n is 4n-6 under the PMC model ( n ≥ 5) and MM^* model ( n ≥ 7) .