Hussain–Niepel–Kinawi's optimal LPDS density conjecture for king grids

About 4 years old · traced to

Let G=(V,E)G=(V,E)) be the infinite king grid with vertex set V=Z×ZV=\mathbb{Z}\times\mathbb{Z}, in which two vertices are adjacent exactly when their Euclidean distance is at most 2\sqrt{2}. For a set S⊆VS\subseteq V, define its density by

D(S)=lim sup⁡k→∞∣S∩NGk[u]∣∣NGk[u]∣,D(S)=\limsup_{k\rightarrow\infty}\frac{|S\cap N_G^k[u]|}{|N_G^k[u]|},

where NGk[u]={x∈V(G)∣d(u,x)≤k}N_G^k[u]=\{x\in V(G)\mid d(u,x)\leq k\} and d(u,x)d(u,x) is graph distance. An optimal locating-paired-dominating set (optimal LPDS) is an LPDS of minimal density. Hussain–Niepel–Kinawi's conjecture. If SS is an optimal LPDS in the king grid and D(S)D(S) is its density, then

D(S)=29.D(S)=\frac{2}{9}.

Previously, the density of an optimal LPDS was known to satisfy 3/14≤D(S)≤2/93/14\leq D(S)\leq 2/9; the conjecture asserts that the upper bound is attained and hence determines the optimal density exactly.

References

Primary source

Yuxuan Yang, “Optimal Locating-Paired-Dominating Sets in King Grids”, arXiv:2210.11838 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.