The strong connectivity of bubble-sort star graphs

Mass data processing and complex problem solving have higher and higher demands for performance of multiprocessor systems. Many multiprocessor systems have interconnection networks as underlying topologies. The interconnection network determines the performance of a multiprocessor system. In the system where the processors and their communication links to each other are likely to fail, it is important to consider the fault tolerance of the network. At this background, the strong connectivity of the network is proposed. For the strong connectivity, it allows both processors and communication links to fail at the same time. For the traditional connectivity, the connectivity only allows processors failure and the edge connectivity only allows communication link failure. In the design of an interconnection network, one of the most fundamental considerations is the connectivity of the network. In this paper, we give the definition of the strong connectivity of the network and some properties of the strong connectivity of the network. As a favorable topology structure of interconnection networks, the n-dimensional bubble-sort star graph BSn has many good properties. We give some strong connectivity of BSn, too.