论文标题
匹配的排除和强烈的匹配排除气泡 - 恒星图
Matching preclusion and strong matching preclusion of the bubble-sort star graphs
论文作者
论文摘要
由于在分布式计算机系统中并行工作的多个处理器，以确保网络的容错和稳定性是分布式系统中的重要问题。由于可以将分布式网络的拓扑结构建模为图形，因此图理论中的（强）匹配排除可以用作并行和分布式网络中缺少边缘的鲁棒性度量，该措施被定义为最小数量的（顶点和）边缘，其在其余网络中既没有完美匹配也不是几乎匹配的匹配的剩余网络。气泡 - 恒星图是与分布式系统相关的有效讨论的互连网络之一。在本文中，我们表明，$ n $二维气泡 - 级星形图的强匹配数量$ bs_n $是$ n \ geq3 $的$ 2 $，每个最佳的强匹配排除$ bs_n $都是从同一品牌组中的两个角度组成的一组。此外，我们表明$ bs_n $的匹配排除号为$ n \ geq3 $ $ 2N-3 $，并且每$ bs_n $的最佳匹配排除集都是微不足道的。
Since a plurality of processors in a distributed computer system working in parallel, to ensure the fault tolerance and stability of the network is an important issue in distributed systems. As the topology of the distributed network can be modeled as a graph, the (strong) matching preclusion in graph theory can be used as a robustness measure for missing edges in parallel and distributed networks, which is defined as the minimum number of (vertices and) edges whose deletion results in the remaining network that has neither a perfect matching nor an almost-perfect matching. The bubble-sort star graph is one of the validly discussed interconnection networks related to the distributed systems. In this paper, we show that the strong matching preclusion number of an $n$-dimensional bubble-sort star graph $BS_n$ is $2$ for $n\geq3$ and each optimal strong matching preclusion set of $BS_n$ is a set of two vertices from the same bipartition set. Moreover, we show that the matching preclusion number of $BS_n$ is $2n-3$ for $n\geq3$ and that every optimal matching preclusion set of $BS_n$ is trivial.
