## Abstract

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph G is the power domination number γ_{P}(G). We show that the power dominating set (PDS) problem is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give a linear algorithm to solve the PDS for trees. In addition, we investigate theoretical properties of γ_{P}(T) in trees T.

Original language | English |
---|---|

Pages (from-to) | 519-529 |

Number of pages | 11 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 15 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jul 2002 |

Externally published | Yes |

## Keywords

- Domination
- Electric power monitoring
- Power domination

## ASJC Scopus subject areas

- General Mathematics