On a new class of identifying codes in graphs

Assume that G=(V,E) is an undirected graph, and C⊆V. For every v∈V, we denote , where d(u,v) denotes the number of edges on any shortest path from u to v. For every F⊆V, we denote Ir(F)=⋃v∈FIr(v). We study codes C with the property that if Ir(F)=Ir(F′) and F≠F′, then both F and F′ have size at least l+1. Such codes can be used in the maintenance of multiprocessor architectures. We consider the cases when G is the infinite square or king grid, infinite triangular lattice or hexagonal mesh, or a binary hypercube.