The Connected Domination Number of Grids

Abstract

Closed form expressions for the domination number of an n×m grid have attracted significant attention, and an exact expression has been obtained in 2011 [7]. In this paper, we present our results on obtaining new lower bounds on the connected domination number of an n×m grid. The problem has been solved for grids with up to 4 rows and with 6 rows and the best currently known lower bound for arbitrary m, n is [11]. Fujie [4] came up with a general construction for a connected dominating set of an n×m grid. In this paper, we investigate whether this construction is indeed optimum. We prove a new lower bound of for arbitrary m,n≥4.