The Domination Number of Grids

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$, $\gamma (G_{n,m})=\lfloor \frac{(n+2)(m+2)}{5}\rfloor -4$.

12 pages, 4 figures

Cited by in corpus (25)

• The 2-domination and Roman domination numbers of grid graphs
• The 2-Domination and 2-Bondage Numbers of Grid Graphs
• The 2-domination number of cylindrical graphs
• On the $2$-domination number of cylinders with small cycles
• HPC acceleration of large (min, +) matrix products to compute domination-type parameters in graphs
• 2-limited broadcast domination on grid graphs
• Signed double Roman domination on cubic graphs
• Powers of large matrices on GPU platforms to compute the Roman domination number of cylindrical graphs
• Connected domination in grid graphs
• Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
• Partial Domination in Graphs
• Boundary Independent Broadcasts in Graphs
• Optimal $(t,r)$ Broadcasts On the Infinite Grid
• Perpetually Dominating Large Grids
• Computing upper bounds for optimal density of $(t,r)$ broadcasts on the infinite grid
• Dominating sequences in grid-like and toroidal graphs
• Properties of Partial Dominating Sets of Graphs
• On the integer {k}-domination number of circulant graphs
• Intensive use of computing resources for dominations in grids and other combinatorial problems
• The Connected Domination Number of Grids
• Quasi-efficient domination in grids
• A general lower bound for the domination number of cylindrical graphs
• Upper broadcast domination of toroidal grids and a classification of diametrical trees
• Lower Bounds for the Exponential Domination Number of $C_m\times C_n$
• An Explicit Construction of Optimal Dominating Sets in Grid