On Vertex-Robust Identifying Codes of Level Three

Abstract

Assume that G = (V, E) is an undirected and connected graph, and consider C subset of V. For every v is an element of V, let 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 between u to v in G. If all the sets I(r)(v) for v is an element of V are pairwise different, and none of them is the empty set, C is called an r-identifying code. In this paper, we consider t-vertex-robust r-identifying codes of level s, that is, r-identifying codes such that they cover every vertex at least s times and the code is vertex-robust in the sense that vertical bar I(r)(u) Delta I(r)(v)vertical bar >= 2t+1 for any two different vertices u and v. Vertex-robust identifying codes of different levels are examined, in particular, of level 3. We give bounds (sometimes exact values) on the density or cardinality of the codes in binary hypercubes and in some infinite grids.