2026/08/03 by Arthur C. Gomes, Yoshiko Wakabayashi
Mathematics · #math.CO #msc:05C69 #msc:90C10 #msc:90C27 #msc:90C35
Comments: AMS-LaTeX, 18 pages with 10 figures
arxiv created 2026/08/03 · arxiv updated 2026/08/04
A set of vertices S of a graph G is locating-dominating if S is dominating and, for each pair of distinct vertices not in S, their neighborhoods in S are distinct. We present results on the minimum density of such sets in the infinite hexagonal grid with a finite number of rows k, also known as the hexagonal strip of width k, which we denote by Hk. For each k≥ 2, we present either an optimal solution or a quasi-optimal solution for Hk that is within 1.3% of the optimum. We describe an exact exponential-time algorithm for fixed k, which we implemented to find optimal solutions for k ≤ 5. As the infinite grid Hk always admits a periodic optimal solution, to deal with larger values of k, we present an integer linear program that finds an optimal periodic solution for Hk for each fixed period. This program yields high-quality feasible solutions for H7 and H8, which we then combine with an optimal solution for H3 to obtain quasi-optimal solutions for all k≥ 6. All these solutions admit a very short description.