Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647153 | Discrete Mathematics | 2015 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Simon Crevals, Patric R.J. Östergård,