Header menu link for other important links
X
The Connected Domination Number of Grids
Published in Springer
2021
Volume: 12601 LNCS
   
Pages: 247 - 258
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. © 2021, Springer Nature Switzerland AG.