Locating-dominating sets on infinite grids with finite height

• Arthur Correia Gomes USP
• Yoshiko Wakabayashi USP

DOI: https://doi.org/10.5753/etc.2025.9150

Resumo

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.

Referências

Bouzinif, M., Darlay, J., Moncel, J., and Preissmann, M. (2019). Exact values for three domination-like problems in circular and infinite grid graphs of small height. Discrete Mathematics & Theoretical Computer Science, Vol. 21 no. 3.

Charon, I., Hudry, O., and Lobstein, A. (2003). Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theor. Comp. Sci., 290(3):2109–2120.

Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., and Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In Graph-Theoretic Concepts in C.S., volume 9224, pages 456–471.

Hartmann, M. E. and Orlin, J. B. (1993). Finding minimum cost to time ratio cycles with small integral transit times. Networks, 23:567–574.

Honkala, I. (2006). An optimal locating-dominating set in the infinite triangular grid. Discrete Mathematics, 306(21):2670–2681.

Honkala, I. and Laihonen, T. (2006). On locating–dominating sets in infinite grids. European Journal of Combinatorics, 27(2):218–227.

Jean, D. (2024). Watching systems, identifying, locating-dominating and discriminating codes in graphs. [link].

Jiang, M. (2018). Periodicity of identifying codes in strips. Information Processing Letters, 135:77–84.

Karp, R. M. (1978). A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3):309–311.

Slater, P. J. (1975). Leaves of trees. In Proc. of the 6th Southw. Conf. on Comb., Graph Theory, and Comput., Congressus Numerantium, volume 14, pages 549–559.

Slater, P. J. (2002). Fault-tolerant locating-dominating sets. Discrete Mathematics, 249(1):179–189. Combinatorics, Graph Theory, and Computing.