论文标题
连接的统治网格数
The Connected Domination Number of Grids
论文作者
论文摘要
$ n \ times m $网格的支配数量的封闭形式表达式引起了极大的关注，并且Gonçalves等人在2011年获得了精确的表达。在本文中，我们介绍了有关在$ n \ times m $网格的连接支配号码上获得新的下限的结果。该问题已解决了最多$ 4 $行的网格，Tolouse等人的$ 6 $行，以及当前最著名的下限$ m，n $是$ \ lceil \ lceil \ frac {mn} {3} {3} \ rceil $。 Fujie提出了一套通用的建筑，用于连接的统治集$ n \ times m $ $ $ \ min \ min \ left \ left \ weft \ {2n+（m-4）+\ lfloor \ frac {m-4} {3} {3} {3} {3} 2m+（n-4）+\ lfloor \ frac {n-4} {3} \ rfloor（m-2）\ right \} $。在本文中，我们研究了这种结构是否确实是最佳的。我们证明了$ \ left \ lceil \ frac {mn+2 \ lceil \ frac {\ min \ {m，n \}} {3} \ rceil} {3} {3} {3} {3} \ right \ rceil $ for nutary $ n \ geq 4 $。
Closed form expressions for the domination number of an $n \times m$ grid have attracted significant attention, and an exact expression has been obtained in 2011 by Gonçalves et al. In this paper, we present our results on obtaining new lower bounds on the connected domination number of an $n \times m$ 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 $\lceil\frac{mn}{3}\rceil$. Fujie came up with a general construction for a connected dominating set of an $n \times m$ grid of size $\min \left\{2n+(m-4)+\lfloor\frac{m-4}{3}\rfloor(n-2), 2m+(n-4)+\lfloor\frac{n-4}{3}\rfloor(m-2) \right\}$ . In this paper, we investigate whether this construction is indeed optimum. We prove a new lower bound of $\left\lceil\frac{mn+2\lceil\frac{\min \{m,n\}}{3}\rceil}{3} \right\rceil$ for arbitrary $m,n \geq 4$.
