On the density of identifying codes in the square lattice

: Honkala I, Lobstein A

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2002

: Journal of Combinatorial Theory, Series B

: JOURNAL OF COMBINATORIAL THEORY SERIES B

: J COMB THEORY B

: 85

: 2

: 297

: 306

: 10

: 0095-8956

DOI: https://doi.org/10.1006/jctb.2001.2106

Let G = (V, E) be an undirected graph and C a subset of vertices. If the sets B-r(nu) boolean AND C, nu is an element of V, are all nonempty and different, where B-r(nu) denotes the set of all points within distance r from nu, we call C an r-identifying code. We give bounds on the best possible density of r-identifying codes in the two-dimensional square lattice. (C) 2002 Elsevier Science (USA).

Mathematics