𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The minimum density of an identifying code in the king lattice

✍ Scribed by Irène Charon; Iiro Honkala; Olivier Hudry; Antoine Lobstein

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
324 KB
Volume
276
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Consider a connected undirected graph G =(V; E) and a subset of vertices C. If for all vertices v ∈ V , the sets Br(v) ∩ C are all nonempty and di erent, where Br(v) denotes the set of all points within distance r from v, then we call C an r-identifying code. For all r, we give the exact value of the best possible density of an r-identifying code in the king lattice, i.e., the inÿnite two-dimensional square lattice with two diagonals.

📜 SIMILAR VOLUMES

On the Density of Identifying Codes in t
On the Density of Identifying Codes in the Square Lattice
✍ Iiro Honkala; Antoine Lobstein 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 148 KB

Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B r (v) 5 C, v ¥ V, are all nonempty and different, where B r (v) denotes the set of all points within distance r from v, we call C an r-identifying code. We give bounds on the best possible density of r-identifying codes in