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\).

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
code; infinite graph
Full Text: EMIS EuDML