Optimal Local Identifying and Local Locating-dominating Codes

: Herva, Pyry; Laihonen, Tero; Lehtilä, Tuomo

Publisher: IOS Press BV

: 2024

: Fundamenta Informaticae

: 191

: 3-4

: 351

: 378

: 1875-8681

DOI: https://doi.org/10.3233/FI-242187

: https://doi.org/10.3233/FI-242187

: https://arxiv.org/pdf/2302.13351

: https://arxiv.org/abs/2302.13351

We introduce two new classes of covering codes in graphs for every positive integer r. These new codes are called local r-identifying and local r-locating-dominating codes and they are derived from r-identifying and r-locating-dominating codes, respectively. We study the sizes of optimal local 1-identifying codes in binary hypercubes. We obtain lower and upper bounds that are asymptotically tight. Together the bounds show that the cost of changing covering codes into local 1-identifying codes is negligible. For some small n optimal constructions are obtained. Moreover, the upper bound is obtained by a linear code construction. Also, we study the densities of optimal local 1-identifying codes and local 1-locating-dominating codes in the infinite square grid, the hexagonal grid, the triangular grid and the king grid. We prove that seven out of eight of our constructions have optimal densities.

:
Research supported by the Emil Aaltonen Foundation. Research supported by the Academy of Finland grant 338797.