On the Density of Identifying Codes in the Square LatticeJournal of Combinatorial Theory, Ser. B, Vol. 85, pp. 297-306, 2002.
Iiro HONKALA
Department of Mathematics
University of Turku
20014 Turku, Finland
e-mail: honkala@utu.fi
&
Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
e-mail: lobstein@infres.enst.fr
Abstract. Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets $B_r(v) \cap C, v \in V$ are all nonempty and different, where $B_r(v)$ denotes the set of all points within distance r from v, 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.