An Optimal Edge-Robust Identifying Code in the Triangular Lattice

摘要

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v)={u ∈C: d(u,v)≤ 1 }, v ∈V, are non-empty and no two of them are the same set. A 1-identifying code C is called 1-edge-robust 1-identifying if it is 1-identifying in every graph G 1 obtained from G by deleting or adding one edge. It is shown that the optimal density of a 1-edge-robust 1-identifying code in the infinite triangular lattice is 3/7.