A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

An improved lower bound for (1,≤2)-identifying codes in the king grid




TekijätFoucaud F, Laihonen T, Parreau A

KustantajaAMER INST MATHEMATICAL SCIENCES

Julkaisuvuosi2014

JournalAdvances in Mathematics of Communications

Tietokannassa oleva lehden nimiADVANCES IN MATHEMATICS OF COMMUNICATIONS

Lehden akronyymiADV MATH COMMUN

Vuosikerta8

Numero1

Aloitussivu35

Lopetussivu52

Sivujen määrä18

ISSN1930-5346

DOIhttps://doi.org/10.3934/amc.2014.8.35


Tiivistelmä

We call a subset C of vertices of a graph G a (1, <= l)-identifying code if for all subset X of vertices with size at most l, the sets {c is an element of C vertical bar there exists u is an element of X, d(u, c) <= 1} are distinct. The concept of identifying codes was in in 1998 by Karpovsky, Chakrabarty and Levitin. Identifying codes have been studied in various grids. In particular, it has been shown that, there exists a (1, <= 2)-identifying code in the king grid with density (3)(7) and that there are no such identifying codes with density smaller than 5/12. Using a suitable frame and a discharging procedure, we improve the lower bound by showing that any (1, <= 2)-identifying code of the king grid has density at least 47/111. This reduces the gap between the best known lower and upper bounds on this problem by more than 56%.




Last updated on 2024-26-11 at 22:04