Exact-Distance Domination in Grid Graphs
2026-07-31 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a grid made of points arranged in an n by n square, and pick special points so that every other point is exactly k steps away from one of them. They focus on finding the smallest number of such special points needed, especially as the grid gets very large. For any fixed distance k, they show bounds on how dense these special points must be in the big grid, with exact values known when k equals 2. This work helps understand how well points can cover a grid at a fixed distance.
square gridvertexgraph theorydistance in graphsdominating setexact-distance k-dominationasymptotic limitcardinalitygrid graphcombinatorics
Authors
Sandip Das, Sweta Das, Arpan Sadhukhan
Abstract
Let \(G_n\) be the \(n\times n\) square grid, and let \(k\geq 2\). A set \(D\subseteq V(G_n)\) is an \emph{exact-distance \(k\)-dominating set} if every vertex \(v\in V(G_n)\setminus D\) has a vertex \(u\in D\) with \(d(u,v)=k\). We write \(D_{\mathrm{opt}}^{(k)}(G_n)\) for the minimum cardinality of such a set. For every fixed \(k\), consider the limit \[ δ_k= \lim_{n\to\infty} \frac{D_{\mathrm{opt}}^{(k)}(G_n)}{n^2}. \] We prove that, for every fixed \(k\geq 3\), \[ \frac{1}{4k} \leq δ_k \leq \frac{k-1}{3k^2-k-1}. \] For \(k=2\), the lower and upper bounds coincide asymptotically, giving \(δ_2=1/9\).