Power domination with bounded time constraints

Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set \(S\) is a power dominating set (PDS) of a graph \(G=(V,E)\) if every vertex \(v\) in \(V\) can be observed under the following two observation rules: (1) \(v\) is dominated by \(S\), i.e., \(v \in S\) or \(v\) has a neighbor in \(S\); and (2) one of \(v\)’s neighbors, say \(u\), and all of \(u\)’s neighbors, except \(v\), can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem.