Analysis reveals locating-dominating set density of 1/3 in square grids up to height 6, indicating expansion of known results.
A locating-dominating set of a graph G is a dominating set C of G such that, for each pair of distinct vertices u and v not in C, the neighborhoods of u and v in C are distinct. We focus on locating-dominating sets of minimum density in the infinite square, triangular and king grids with finite height. Optimal results on these grids were known only for height up to 3. We extend these results showing optimal solutions with density 1/3 for square grids with height 4, 5 and 6, and show how locating-dominating sets with density 1/3 can be obtained for any square grid with finite height. We also show optimal solutions for the infinite triangular and king grids with heights 4 and 5.
No takes yet. Share an insight, caveat, or question.
Gomes et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: