Power Domination Problem In Graphs

Let G=(V, E) be a simple connected graph. A vertex subset S C V is a power dominating set of G if all vertices in V are "observed" by the vertices in S. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. The power domination number, denoted by γp(G), is the minimum cardinality of a power dominating set. A minimum power dominating set of G, denoted by γp(G)-set, is a power dominating set S with cardinality γp(G).The power domination problem is to determine the power domination number for a given graph. It was first proposed by T.W. Haynes et al., and they prove that it is NP-complete for general graphs. In this paper, based on the previous theoretical results, we do a systematic research on power domination problem.It is well-known that the perfect graphs are the main research objects of Graph Theory. We do a study on the power domination problem for the perfect graphs in Chapter2. To solve the power domination problem and the к-power domination problem for trees, we put forward two linear labeling algorithms, an improvement over the present algorithms; for vertex-weighted trees, we present a linear dynamic programming algorithm.To solve the power domination problem for block graphs, we give a linear labeling algorithm, an improvement over the known algorithm. The algorithm manipulates the block graph directly, saving the conversion steps. Moreover, the root node of the vertex ordering can be selected arbitrarily. In addition, the first linear labeling algorithm to solve the к-power domination problem for block graphs is presented.To solve the power domination problem for interval graphs, we present a linear labeling algorithm, which depends on only one vertex ordering, an improvement over the known algorithm.In Chapter3, we analyze the complexity of the power domination problem. By giving a reduction from domination problem, we come to the conclusion that the power domination problem is NP-complete.In Chapter4, we describe the previous results on the other special graph classes, including the Cartesian product of paths and cycles, and generalized Petersen graphs. We also describe an algorithm used to solve power domination problem on grids...