Efficient Domination in Grid Graphs

Let G = ( V , E ) be a graph. A subset S ⊆ V of vertices is an efficient dominating set if every vertex v ∈ V is adjacent to exactly one vertex in S , where a vertex u ∈ S is considered to be adjacent to itself. Efficient domination is highly desirable in many real-world applications, and yet, in general, graphs are often not efficient. It is of value, therefore, to determine optimum ways in which inefficient graphs can be changed in order to make them efficient. It is well known, for example, that almost no m × n grid graphs have efficient dominating sets. In this paper, we consider the minimum number of vertices that can be removed from an m × n grid graph so that the remaining graph has an efficient dominating set.