The tightly super 3-extra connectivity and 3-extra diagnosability of crossed cubes

Abstract

Many multiprocessor systems have interconnection networks as underlying topologies and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors. 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 $C{Q}_n$ has many good properties. In this paper, we prove that $C{Q}_n$ is tightly $(4n-9)$ super 3-extra connected for $n\ge 7$ and the 3-extra diagnosability of $C{Q}_n$ is $4n-6$ under the PMC model $(n\ge 5)$ and MM${}^{\ast }$ model $(n\ge 7)$.