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