Premium
The node cop‐win reliability of unicyclic and bicyclic graphs
Author(s) -
Ahmed Maimoonah,
Cameron Ben
Publication year - 2022
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22055
Subject(s) - combinatorics , graph , random graph , mathematics , discrete mathematics , computer science
Abstract 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.