Identifying Codes with Small Radius in Some Infinite Regular Graphs

Abstract

Let $G=(V,E)$ be a connected undirected graph and $S$ a subset of vertices. If for all vertices $v \in V$, the sets $B_r(v) \cap S$ are all nonempty and different, where $B_r(v)$ denotes the set of all points within distance $r$ from $v$, then we call $S$ an $r$-identifying code. We give constructive upper bounds on the best possible density of $r$-identifying codes in four infinite regular graphs, for small values of $r$.