On Vertex-Robust Identifying Codes of Level Three

Abstract

Assume that \(G = (V, E)\) is an undirected and connected graph, and consider \(C \subseteq V\). For every \(v \in V\), let \(I_r(v) = \{u \in C: d(u,v) \leq 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 \in 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 \(|I_r(u) \Delta I_r(v)| \geq 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.