Title: Minimum-density locating-dominating sets on infinite graphs
Student: Arthur Correia Gomes
Advisor: Yoshiko Wakabayashi

Data: segunda-feira, 26 de maio de 2025
Time: 15h
Place: Auditório Antonio Gilioli - Bloco A

Abstract: The central topic of this master’s thesis proposal is the study of minimum-density locating- dominating sets on infinite graphs. In a graph G = (V,E), a set C ⊆ V is locating-dominating if, for each vertex v ∈ V \ C, we have N(v) ∩ C ≠ ∅, and for each pair of distinct vertices u,v ∈ V \ C, we have N(u) ∩ C ≠ N(v) ∩ C, where N(v) is the (open) neighborhood of vertex v. When working with infinite graphs, the goal is to find a locating-dominating set with minimum density. This problem is known to be NP-hard even for very special classes of graphs. There has been extensive research on finite graphs, both in the general case and for specific graph classes. On the other hand, for infinite graphs, the studies have concentrated mostly on regular grids. Only a few results are known for regular grids with a finite number of rows. This motivated us to study some classes of (infinite) regular grids with a finite number of rows, with emphasis on the hexagonal grids, for which no result has been mentioned in the literature.