An explicit construction of optimal dominating and [1,2]-dominating sets in grid

Abstract

A dominating set in a graph G is a subset of vertices D such that every vertex in V\D is a neighbor of some vertex of D. The domination number of G is the minimum size of a dominating set of G and it is denoted by gamma (G). A dominating set with cardinality gamma (G) is called optimal dominating set. Also, a subset D of a graph G is a [1, 2]-set if, each vertex v is an element of V\D is adjacent to either one or two vertices in D and the minimum cardinality of [1, 2]-dominating set of G, is denoted by gamma [1,2](G). Chang's conjecture says that for every 16 <= m <= n,gamma (Gm,n)=(n+2)(m+2)5-4 and this conjecture has been proven by Goncalves et al. This paper presents an explicit constructing method to find an optimal dominating set for grid graph G(m)(,)(n) where m,n >= 16 in O (size of answer). In addition, we will show that gamma (Gm,n)=gamma [1,2](Gm,n) where m,n >= 16 holds in response to an open question posed by Chellali et al.