On codes identifying vertices in the two-dimensional square lattice with diagonals

Authors
Cohen, GD Honkala, I Lobstein, A Zemor, G
Citation
Gd. Cohen et al., On codes identifying vertices in the two-dimensional square lattice with diagonals, IEEE COMPUT, 50(2), 2001, pp. 174-176
Citations number
9
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON COMPUTERS
ISSN journal
00189340 → ACNP
Volume
50
Issue
2
Year of publication
2001
Pages
174 - 176
Database
ISI
SICI code
0018-9340(200102)50:2<174:OCIVIT>2.0.ZU;2-1
Abstract
Fault diagnosis of multiprocessor systems motivates the following graph-the oretic definition. A subset C of points in an undirected graph G = (V, E) i s called an identifying code if the sets B(upsilon) boolean AND C consistin g of all elements of C within distance one from the vertex upsilon are diff erent. We also require that the sets B(upsilon) boolean AND C are all nonem pty. We take G to be the infinite square lattice with diagonals and show th at the density of the smallest identifying code is at least 2/9 and at most 4/17.