Bounds for codes identifying vertices in the hexagonal grid

: Cohen GD, Honkala I, Lobstein A, Zemor G

Publisher: SIAM PUBLICATIONS

: 2000

: Siam Journal on Discrete Mathematics

: SIAM JOURNAL ON DISCRETE MATHEMATICS

: SIAM J DISCRETE MATH

: 13

: 4

: 492

: 504

: 13

: 0895-4801

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

In an undirected graph G = (V, E), a subset C subset of or equal to V is called an identifying code if the sets B-1 (v) boolean AND C consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.

Mathematics