星图的R¹-限制性点割

The R¹-Restricted Cuts of Star Graphs

摘要: 互联网络的拓扑结构可以用图论模型来描述，因此图论在研究网络问题时扮演着重要角色。连通度是衡量一个网络容错性和可靠性的重要指标。然而，在实际情况中，网络中一个点的所有邻点同时发生故障的概率较小，因此经典连通度在一定程度上低估了互联网络的容错性。为了更准确地评估网络的连通性，引入了条件连通度的概念，并进一步提出了R^k-连通度的概念，使得连通度问题更具有现实意义。本文主要研究并刻画了星图的全部基数最小的R¹-限制性点割。

Abstract: The topology of the Internet can be described using graph theory models, thus graph theory plays an important role in studying network issues. Connectivity is a crucial metric for assessing the fault tolerance and reliability of a network. However, in practical scenarios, the probability of all neighbors of a node in the network failing simultaneously is very small. Therefore, classic connectivity to some extent underestimates the fault tolerance of the Internet. To more accurately evaluate network connectivity, the concept of conditional connectivity has been introduced, and further, the concept of R^k-connectivity has been proposed, making the connectivity problem more practically significant. This paper primarily studies and characterizes the minimum cardinality R¹-restricted cut of star graphs.