Domination in Graphs Applied to Electric Power Networks
Document Type
Article
Publication Date
7-1-2002
Description
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.
Citation Information
Haynes, Teresa W.; Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; and Henning, Michael A.. 2002. Domination in Graphs Applied to Electric Power Networks. SIAM Journal on Discrete Mathematics. Vol.15(4). 519-529. https://doi.org/10.1137/S0895480100375831 ISSN: 0895-4801