叶形图的强连通性

The Strong Connectivity of Leaf-Sort Graphs

摘要: 一个互联网络系统通常会被构建成一个无向连通图G = (V (G), E(G))，其中V (G)代表图的顶点集， E(G)代表着图的边集，顶点和边分别代表着互联网络中的处理器和处理器之间的通信链路。 在互 联网络中，处理器或者通信链路出现故障是不可避免的，在这种系统中，我们重点考虑网络的容 错能力。 而连通性在衡量互联网络的容错性和可靠性方面起着重要作用。 传统的连通性只可允许 处理器或者通信链路发生故障，它的适用范围比较局限。在此背景下，提出了网络的强连通性。强 连通性允许处理器和通信链路可以同时发生故障，它是传统连通性的衍生。 显然更适用于一般情 况。 叶形图有很多好的性质，本文研究了叶形图的一些强连通性，并且得到了叶形图的强连通度 以及强自然连通度。

Abstract: An interconnection network is usually modeled as an undirected, connected graph G = (V (G), E(G)), where V (G) represents vertex set, V (G) represents edge set, and nodes represent processors, edges represent communication links between processors. In the interconnect network, the failure of processors or communication links is un- avoidable. We focus on the fault tolerance of the network. The connectivity plays an important role in measuring the fault tolerance and reliability of interconnection networks. Traditional connectivity only allows processor or communication link to fail, its scope of application is relatively limited. Under this background, the strong connectivity of the network is proposed. Strong connectivity allows both the processor and the communication link to fail at the same time and is a derivative of traditional connectivity. Obviously more applicable to general situations. Leaf graphs have many good properties. In this paper, we study some strong connectivity of leaf graphs, and the strong connectivity and strong natural connectivity of leaf graphs are obtained.