A note on power domination in grid graphs

Michael Dorfling, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

75 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 (see [T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, M.A. Henning, Power domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15(4) (2002) 519-529]). A set S of vertices is defined 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 is its power domination number. In this paper, we determine the power domination number of an n×m grid graph.

Original languageEnglish
Pages (from-to)1023-1027
Number of pages5
JournalDiscrete Applied Mathematics
Volume154
Issue number6
DOIs
Publication statusPublished - 15 Apr 2006
Externally publishedYes

Keywords

  • Grid
  • Power domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A note on power domination in grid graphs'. Together they form a unique fingerprint.

Cite this