Back to Search Start Over

On identification in the triangular grid

Authors :
Iiro S. Honkala
Tero Laihonen
Source :
Journal of Combinatorial Theory, Series B. 91:67-86
Publication Year :
2004
Publisher :
Elsevier BV, 2004.

Abstract

A subset C of vertices in a connected graph G=(V,E) is called (r,⩽l)-identifying if for all subsets L⊆V of size at most l, the sets I(L), consisting of all the codewords which are within graphic distance r from at least one element in L, are different. It is proved that the minimum possible density of a (1,⩽2)-identifying code in the triangular grid is 9/16.

Details

ISSN :
00958956
Volume :
91
Database :
OpenAIRE
Journal :
Journal of Combinatorial Theory, Series B
Accession number :
edsair.doi.dedup.....cf3cf96f16a7a1f2b43d94df3ec6e43b
Full Text :
https://doi.org/10.1016/j.jctb.2003.10.002