Domination in graphs applied to electric power networks

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

271 Citations (Scopus)

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 languageEnglish
Pages (from-to)519-529
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume15
Issue number4
DOIs
Publication statusPublished - Jul 2002
Externally publishedYes

Keywords

  • Domination
  • Electric power monitoring
  • Power domination

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Domination in graphs applied to electric power networks'. Together they form a unique fingerprint.

Cite this