Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6697| Title: | The Connected Domination Number of Grids |
| Authors: | SRINIVASAN, ADARSH Narayanaswamy, N. S. Mudgal, Apurva Subramanian, C. R. Dept. of Mathematics |
| Keywords: | Connected dominating set Maximum leaf spanning tree Grid graph Connected domination number 2021 |
| Issue Date: | Jan-2021 |
| Publisher: | Springer Nature |
| Citation: | CALDAM 2021: Algorithms and Discrete Applied Mathematics pp 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. |
| URI: | https://link.springer.com/chapter/10.1007/978-3-030-67899-9_19 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6697 |
| Appears in Collections: | BOOK CHAPTERS |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.