论文标题
单周期和双环图的节点COP-WIN可靠性
The node cop-win reliability of unicyclic and bicyclic graphs
论文作者
论文摘要
已经研究了各种模型来量化网络的可靠性，而图表的某些组件可能会随机失败，并且连接其余图的概率是可靠性的代理。在这项工作中，我们通过考虑剩余图不仅连接而是Cop-Win的概率来介绍其中一个模型的加强。如果一个警察可以保证在经过深思熟虑的警察和强盗的追捕游戏中捕获逃离的强盗，则一张图形是冠军。更确切地说，对于一个带有概率$ p $的节点的图形$ g $，当且仅当它们两个终点都在运行时，这些节点是独立运行的，而$ g $的节点可靠性为$ g $，表示$ \ text {ncrel}（g，p）$，是cop $ $ g $ $ g的可能性。然后，找到带有$ n $ nodes和$ m $ nodes的图形$ g $和$ \ text {ncrel}（g，p）\ ge \ ge \ ge \ text {ncrel}（h，p）$ for in [0,1] $ in [0,1] $ in [0,1] $，以及所有图形$ h $ n $ n $ nodes＆n $ n $ m $ and $ n $ m $。这样的图称为统一最可靠的。我们表明，分别针对单周期和双环图的最可靠图。这与没有知道最大化节点可靠性概念的稀疏图相反。
Various models to quantify the reliability of a network have been studied where certain components of the graph may fail at random and the probability that the remaining graph is connected is the proxy for reliability. In this work we introduce a strengthening of one of these models by considering the probability that the remaining graph is not just connected but also cop-win. A graph is cop-win if one cop can guarantee capture of a fleeing robber in the well-studied pursuit-evasion game of Cops and Robber. More precisely, for a graph $G$ with nodes that are operational independently with probability $p$ and edges that are operational if and only if both of their endpoints are operational, the node cop-win reliability of $G$, denoted $\text{NCRel}(G,p)$, is the probability that the operational nodes induce a cop-win subgraph of $G$. It is then of interest to find graphs $G$ with $n$ nodes and $m$ edges such that $\text{NCRel}(G,p)\ge\text{NCRel}(H,p)$ for all $p\in[0,1]$ and all graphs $H$ with $n$ nodes and $m$ edges. Such a graph is called uniformly most reliable. We show that uniformly most reliable graphs exist for unicyclic and bicyclic graphs, respectively. This is in contrast to the fact that there are no known sparse graphs maximizing the corresponding notion of node reliability.
