# zbMATH — the first resource for mathematics

New bounds for codes identifying vertices in graphs. (English) Zbl 0917.05058
Electron. J. Comb. 6, No. 1, Research paper R19, 14 p. (1999); printed version J. Comb. 6, 283-296 (1999).
Suppose $$G$$ is an undirected graph and $$C$$ a subset of the vertices of $$G$$ which is called a code. For any vertex $$v$$ of $$G$$, the neighboring set is the set of vertices in $$C$$ at a distance at most 1 from $$v$$. The code $$C$$ is said to identify the vertices of $$G$$ if the neighboring sets are all nonempty and different. The authors consider $$G$$ a square grid drawn on a torus and establish the minimum density $$D$$ of an identifying code of the limiting infinite graph as $$23/66\leq D\leq 5/14$$.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 68R10 Graph theory (including graph drawing) in computer science 94B99 Theory of error-correcting codes and error-detecting codes 94C12 Fault detection; testing in circuits and networks
##### Keywords:
code; infinite graph
Full Text: