The g-extra connectivity and diagnosability of crossed cubes

摘要

Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-extra connectivity of G. In 2016, Zhang et al. proposed the g-extra diagnosability of G that requires every component of G−S has at least (g+1) vertices. The g-extra connectivity of G is necessary for g-extra diagnosability of G. In this paper, we show that the g-extra connectivity of the crossed cube CQn is n(g+1)−12g(g+3) for n ≥ 5, 0≤g≤⌊n2⌋ and the g-extra diagnosability of CQn is (n−12g)(g+1) under the PMC model for n ≥ 5, 0≤g≤⌊n2⌋ and the MM* model for n ≥ 7, 0≤g≤⌊n2⌋.