On a new class of identifying codes in graphs

Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, we denote I-r(v) = {u is an element of C: d(u, v) <= r}, where d(u, v) denotes the number of edges on any shortest path from u to v. For every F subset of V, we denote I-r(F) = boolean OR(v is an element of F) I-r(v). We study codes C with the property that if I-r(F) = I-r(F') and F not equal 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. (c) 2006 Elsevier B.V. All rights reserved.