2017/07/20 by Sharifani, P., Hooshmandasl, M. R., Meybodi, M. Alambardar
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1707.06471
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 γ(G). Also, a subset D of a graph G is a [ 1 , 2 ] -set if, each vertex v ∈ 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 γ[1,2](G). Chang's conjecture says that for every 16 ≤ m ≤ n, γ(Gm,n)= \lfloor((n+2)(m+2))/(5) \rfloor-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 Gm,n where m,n≥ 16 in O(size of answer). In addition, we will show that γ(Gm,n)=γ[1,2](Gm,n) where m,n≥ 16 holds in response to an open question posed by Chellali et al.