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)\le 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)\mathrm{\Delta }{I}_r(v)|\ge 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.