泡型图的强连通性  

The Strong Connectivity of Bubble-Sort Graphs

作　　者：郭小丽 王世英 

机构地区：[1]山西师范大学数学与计算机科学学院,山西 太原

出　　处：《应用数学进展》2024年第3期1156-1175,共20页Advances in Applied Mathematics

摘　　要：一个互联网络系统通常由一个简单无向连通图 G = (V (G), E(G)) 构成,其中 V (G) 和 E(G) 分别 表示互联网络中的处理器和处理器之间的通信链路。 在互联网络中,处理器或者通信链路出现故 章是不可避免的,而连通性和边连通性是评估互联网络容错性和可靠性的主要参数。 基于这种情 况,提出了互联网络的强连通性,强连通性允许处理器和通信链路同时发生故章。 在本文中,我 们研究了当 n ≥ 4 时,n-维泡型图 Bn 的强连通性和强自然连通性以及强自然边连通性等相关性 质。A network is usually modeled by a simple undirected graph G = (V (G), E(G)), where V (G) and E(G) represent processors and links between processors, respectively. In the interconnect network, the failure of processors or communication links is unavoidable. The connectivity and edge-connectivity of G are major parameters to evaluate the fault-tolerance and reliability of a network. Based on such circumstances, strong connectivity of the internet is proposed, it allows both processors and links to fail at the same time. In this paper, we study strong connectivity of Bn for n ≥ 4, including the strong natural connectivity and strong natural edge-connectivity of Bn and so on.

关 键 词：连通性 强连通性 强自然连通性 泡型图 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]