The minimum density of an identifying code in the king lattice

Irène Charon; Iiro Honkala; Olivier Hudry; Antoine Lobstein

doi:10.1016/S0012-365X(03)00306-6

The minimum density of an identifying code in the king lattice

Irène Charon
, Iiro Honkala
, Olivier Hudry
, Antoine Lobstein

Research output: Contribution to journal › Article › peer-review

Abstract

Consider a connected undirected graph G = (V,E) and a subset of vertices C. If for all vertices v ε V, the sets B_r(v)∩C are all nonempty and different, where B_r(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 infinite two-dimensional square lattice with two diagonals.

Original language	English
Pages (from-to)	95-109
Number of pages	15
Journal	Discrete Mathematics
Volume	276
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(03)00306-6
Publication status	Published - 6 Feb 2004

Keywords

Graph theory
Identifying codes

Access to Document

10.1016/S0012-365X(03)00306-6

Cite this

@article{0d802d7b2de240e88140b491d6e0a15e,

title = "The minimum density of an identifying code in the king lattice",

abstract = "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 different, 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 infinite two-dimensional square lattice with two diagonals.",

keywords = "Graph theory, Identifying codes",

author = "Ir{\`e}ne Charon and Iiro Honkala and Olivier Hudry and Antoine Lobstein",

year = "2004",

month = feb,

day = "6",

doi = "10.1016/S0012-365X(03)00306-6",

language = "English",

volume = "276",

pages = "95--109",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "1-3",

}

TY - JOUR

T1 - The minimum density of an identifying code in the king lattice

AU - Charon, Irène

AU - Honkala, Iiro

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2004/2/6

Y1 - 2004/2/6

N2 - 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 different, 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 infinite two-dimensional square lattice with two diagonals.

AB - 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 different, 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 infinite two-dimensional square lattice with two diagonals.

KW - Graph theory

KW - Identifying codes

U2 - 10.1016/S0012-365X(03)00306-6

DO - 10.1016/S0012-365X(03)00306-6

M3 - Article

AN - SCOPUS:0346154875

SN - 0012-365X

VL - 276

SP - 95

EP - 109

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

The minimum density of an identifying code in the king lattice

Abstract

Keywords

Access to Document

Fingerprint

Cite this