The Connected Domination Number of Grids

DOI10.1007/978-3-030-67899-9_19MaRDI QIDQ6354327arXivFDO

Authors Adarsh Srinivasan, N. S. Narayanaswamy

Publication date 23 November 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-67899-9_19

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

arXiv classification

cs.DMmath.CO

Abstract: Closed form expressions for the domination number of an $nimesm$ grid have attracted significant attention, and an exact expression has been obtained in 2011 by Gonc{c}alves et al. In this paper, we present our results on obtaining new lower bounds on the connected domination number of an $nimesm$ grid. The problem has been solved for grids with up to $4$ rows and with $6$ rows by Tolouse et al and the best currently known lower bound for arbitrary $m,n$ is $lceilfracmn3ceil$. Fujie came up with a general construction for a connected dominating set of an $nimesm$ grid of size $minleft2n+(m-4)+lfloorfracm-43floor(n-2),2m+(n-4)+lfloorfracn-43floor(m-2)ight$ . In this paper, we investigate whether this construction is indeed optimum. We prove a new lower bound of $leftlceilfracmn+2lceilfracminm,n3ceil3ightceil$ for arbitrary $m,ngeq4$.

This page was built for publication: The Connected Domination Number of Grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354327)