Identifying codes and searching with balls in graphs

Abstract

Given a graph $G$ and a positive integer $R$ we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form "does an unknown vertex $v\in V(G)$ belong to the ball of radius $r$ around $u$?" with $u\in V(G)$ and $r\le R$ that is needed to determine $v$. We consider both the adaptive case when the $j$th query might depend on the answers to the previous queries and the non-adaptive case when all queries must be made at once. We obtain bounds on the minimum number of queries for hypercubes, the Erd\H os-Rényi random graphs and graphs of bounded maximum degree .