Universal Graph Model of Cyclic Networks and Their Reliability

In the present paper, we extend the domination theory to cyclic monotone graphs, which are a universal graph model for the analysis of complex-structured system reliability. In particular, we derive a formula for calculating the reliability of arbitrary monotone graphs, which reduces the system level of reliability analysis to the element level. As a corollary, we prove that for any fixed integer $k$ the problem of calculating the reliability of monotone graphs of degree $k$ can be solved in a time that polynomially depends on the dimension of graphs and the number of their acyclic monotone subgraphs. At the same time, we show that the reliability determination problem is $NP$-hard even in the class of acyclic $dc$-trivial monotone graphs of degree 2 with the number of minimal acyclic subgraphs being proportional to the graph vertex number.