The Tightly Super 2-good-neighbor connectivity and 2-good-neighbor Diagnosability of Crossed Cubes

Shiying Wang, Xiaolei Ma, Yunxia Ren

The reliability of an interconnection network is an important issue for multiprocessor systems. We know that connectivity and the diagnosability are two important parameters for measuring the reliability of an interconnection network. In 2012, Peng et al. proposed the g-good-neighbor diagnosability, which has been widely accepted as a new measure of the diagnosability by restricting that every fault-free vertex contains at least g fault-free neighbors. As an important variant of the hypercube, the n-dimensional crossed cube CQ_n has many good properties. In this paper, we show that (1) the 2-good-neighbor connectivity of  CQ_n is 4n-8 for n≥4, (2) CQ_n is tightly (4n-8) super 2-good-neighbor connected for n≥6 and (3) the 2-good-neighbor diagnosability of  CQ_n is 4n-5 under the PMC model and MM* model for n≥4 .