Daniel Gonçalves, Alexandre Pinlou, Michael Rao, Stéphan Thomassé
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
In this paper, we conclude the calculation of the domination number of all $n\times m$ grid graphs. Indeed, we prove Chang's conjecture saying that for every $16\le n\le m$, $γ(G_{n,m})=\lfloor\frac{(n+2)(m+2)}{5}\rfloor -4$.
arXiv comments
12 pages, 4 figures
Journal reference
SIAM Journal of Discrete Mathematics, vol. 25, pp. 1443-1453, 2011
It turns out that the answer to this question is known for all sizes of grid[1], though it was found fairly recently (2011) and the answer for small grids is quite complicated. For the 9x4 grid, the optimal number is indeed 10. For large n×m grids, with n and m ≥ 16, the minimum…
It turns out that the answer to this question is known for all sizes of grid[1], though it was found fairly recently (2011) and the answer for small grids is quite complicated. For the 9x4 grid, the optimal number is indeed 10. For large n×m grids, with n and m ≥ 16, the minimum…
robinhoustonView on HNParent context