轮图的强连通性

The Strong Connectivity of the Wheel Network

摘要: 互连网络在大型多处理器系统中扮演着重要的角色，许多多处理器系统都有互连网络作为底层拓扑，网络通常用图来表示。在处理器及其彼此之间的通信链路可能发生故障的系统中，重要的是要考虑网络的容错能力。在此背景下，提出了网络的强连通性。为了实现强连通性，它允许处理器和通信链路同时发生故障。一个图G的强0-好邻连通性也称为图G的强连通性，同时我们把一个图G的强1-好邻连通性也称为图G的强自然连通性。本文在n-维泡型星图BSn强连通性的基础上研究了当n ≥ 4时，CW_n的一些强连通性，其中包括CW_n的强0-好邻连通性、强自然连通性以及强自然边连通性等相关性质。

Abstract: Interconnect network plays an important role in large multiprocessor system, many multiprocessor systems have an interconnect network as the underlying topology, and the network is usually rep-resented by a graph. In systems where the processors and their communication links to each other can fail, it is important to consider the fault tolerance of the network. Under this background, the strong connectivity of network is proposed. To achieve strong connectivity, it allows both the pro-cessor and the communication link to fail simultaneously. The strong 0-good-neighbor connectivity of a graph G is also called the strong connectivity of a graph G, and the strong 1-good-neighbor con-nectivity of a graph G is also called the strong natural connectivity of a graph G. In this paper, based on the strong connectivity property of n-dimensional bubble-sort star graph BSn, we study some strong connectivity of CW_n for n ≥ 4, including the strong 0-good-neighbor connectivity, strong nat-ural connectivity and strong natural edge connectivity of CW_n and soon.