New bounds for codes identifying vertices in graphs
The electronic journal of combinatorics, Tome 6 (1999)
Let $G=(V,E)$ be an undirected graph. Let $C$ be a subset of vertices that we shall call a code. For any vertex $v\in V$, the neighbouring set $N(v,C)$ is the set of vertices of $C$ at distance at most one from $v$. We say that the code $C$ identifies the vertices of $G$ if the neighbouring sets $N(v,C), v\in V,$ are all nonempty and different. What is the smallest size of an identifying code $C$ ? We focus on the case when $G$ is the two-dimensional square lattice and improve previous upper and lower bounds on the minimum size of such a code.
@article{10_37236_1451,
author = {G\'erard Cohen and Iiro Honkala and Antoine Lobstein and Gilles Z\'emor},
title = {New bounds for codes identifying vertices in graphs},
journal = {The electronic journal of combinatorics},
year = {1999},
volume = {6},
doi = {10.37236/1451},
zbl = {0917.05058},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1451/}
}
TY - JOUR AU - Gérard Cohen AU - Iiro Honkala AU - Antoine Lobstein AU - Gilles Zémor TI - New bounds for codes identifying vertices in graphs JO - The electronic journal of combinatorics PY - 1999 VL - 6 UR - http://geodesic.mathdoc.fr/articles/10.37236/1451/ DO - 10.37236/1451 ID - 10_37236_1451 ER -
Gérard Cohen; Iiro Honkala; Antoine Lobstein; Gilles Zémor. New bounds for codes identifying vertices in graphs. The electronic journal of combinatorics, Tome 6 (1999). doi: 10.37236/1451
Cité par Sources :