New bounds for codes identifying vertices in graphs (Q1283874): Difference between revisions

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