A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Bounds for codes identifying vertices in the hexagonal grid
Tekijät: Cohen GD, Honkala I, Lobstein A, Zemor G
Kustantaja: SIAM PUBLICATIONS
Julkaisuvuosi: 2000
Journal: Siam Journal on Discrete Mathematics
Tietokannassa oleva lehden nimi: SIAM JOURNAL ON DISCRETE MATHEMATICS
Lehden akronyymi: SIAM J DISCRETE MATH
Vuosikerta: 13
Numero: 4
Aloitussivu: 492
Lopetussivu: 504
Sivujen määrä: 13
ISSN: 0895-4801
DOI: https://doi.org/10.1137/S0895480199360990
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali