Article ID Journal Published Year Pages File Type
4647153 Discrete Mathematics 2015 6 Pages PDF
Abstract

Let im,nim,n denote the minimum size of an independent dominating set in the mm-by-nn grid. In this article a dynamic programming algorithm is described that computes im,nim,n for fixed mm and arbitrary nn. For m<16m<16, the algorithm is used to determine im,nim,n as a function of nn. For m,n≥16m,n≥16, it is proved that im,n=⌊(m+2)(n+2)/5⌋−4im,n=⌊(m+2)(n+2)/5⌋−4 by constructing corresponding independent dominating sets and by applying results on the minimum size of dominating sets. Thus the independent domination number is now known for all grids.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,