A1 Refereed original research article in a scientific journal
Bounds for codes identifying vertices in the hexagonal grid
Authors: Cohen GD, Honkala I, Lobstein A, Zemor G
Publisher: SIAM PUBLICATIONS
Publication year: 2000
Journal: Siam Journal on Discrete Mathematics
Journal name in source: SIAM JOURNAL ON DISCRETE MATHEMATICS
Journal acronym: SIAM J DISCRETE MATH
Volume: 13
Issue: 4
First page : 492
Last page: 504
Number of pages: 13
ISSN: 0895-4801
DOI: https://doi.org/10.1137/S0895480199360990
Abstract
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.
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.
UTU Research Portal