Locating-dominating sets on infinite grids with finite height - Gomes, Arthur Correia; Wakabayashi, Yoshiko (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
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.