On identifying codes in the triangular and square grids

: Honkala I, Laihonen T

Publisher: SIAM PUBLICATIONS

: 2004

: SIAM Journal on Computing

: SIAM JOURNAL ON COMPUTING

: SIAM J COMPUT

: 33

: 2

: 304

: 312

: 9

: 0097-5397

DOI: https://doi.org/10.1137/S0097539703433110

It is shown that in the infinite square grid the density of every (r,less than or equal to 2)-identifying code is at least 1/8 and that there exists a sequence C-r of (r, less than or equal to 2)-identifying codes such that the density of C-r tends to 1/8 when r --> infinity. In the infinite triangular grid a sequence C'(r) of (r, less than or equal to 2)-identifying codes is given such that the density of C'(r) tends to 0 when r --> infinity.

Mathematics