Elsevier

Discrete Applied Mathematics

Volume 154, Issue 6, 15 April 2006, Pages 1023-1027
Discrete Applied Mathematics

Note
A note on power domination in grid graphs

https://doi.org/10.1016/j.dam.2005.08.006Get rights and content
Under an Elsevier user license
open archive

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.

Keywords

Grid
Power domination

Cited by (0)

1

Research supported in part by the South African National Research Foundation.

2

Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.