The node cop‐win reliability of unicyclic and bicyclic graphs

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. We introduce a strengthening of one of these models by considering the probability that the remaining graph is cop‐win. A graph is cop‐win if one cop can win the game Cops and Robber. More precisely, for a graph G with nodes that are operational independently with probability p , the node cop‐win reliability of G , denoted 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 NCRel ( G , p ) ≥ NCRel ( H , p ) for all p  ∈ [0, 1] and all graphs H with n nodes and m edges. We show that such graphs exist among unicyclic and bicyclic graphs, respectively.