The minimum density of an identifying code in the king lattice

: Charon I, Honkala I, Hudry O, Lobstein A

Publisher: ELSEVIER SCIENCE BV

: 2004

: Discrete Mathematics

: DISCRETE MATHEMATICS

: DISCRETE MATH

: 276

: 1-3

: 95

: 109

: 15

: 0012-365X

DOI: https://doi.org/10.1016/S0012-365X(03)00306-6

Consider a connected undirected graph G =(V, E) and a subset of vertices C. If for all vertices v is an element of V, the sets B-r(v) boolean AND C are all nonempty and different, where B-r(v) denotes the set of all points within distance r from v, then we call C an r-identifying code. For all r, we give the exact value of the best possible density of an r-identifying code in the king lattice, i.e., the infinite two-dimensional square lattice with two diagonals. (C) 2003 Published by Elsevier B.V.

Mathematics