Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach

Abstract

In this text, we prove the existence of an asymptotic growth rate of the number of dominating sets (and variants) on finite rectangular grids, when the dimensions of the grid grow to infinity. Moreover, we provide, for each of the variants, an algorithm which computes the growth rate. We also give bounds on these rates provided by a computer program.

19 pages, 11 figures v2 corrects a about the entropy and the growth rate (they are not equal: one is the log of the other)