A1 Refereed original research article in a scientific journal
The minimum density of an identifying code in the king lattice
Authors: Charon I, Honkala I, Hudry O, Lobstein A
Publisher: ELSEVIER SCIENCE BV
Publication year: 2004
Journal: Discrete Mathematics
Journal name in source: DISCRETE MATHEMATICS
Journal acronym: DISCRETE MATH
Volume: 276
Issue: 1-3
First page : 95
Last page: 109
Number of pages: 15
ISSN: 0012-365X
DOI: https://doi.org/10.1016/S0012-365X(03)00306-6(external)
Abstract
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.
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.