Identifying codes and searching with balls in graphs

Given a graph GG and a positive integer RR we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form “does an unknown vertex v∈V(G)v∈V(G) belong to the ball of radius rr around uu?” with u∈V(G)u∈V(G) and r≤Rr≤R that is needed to determine vv. We consider both the adaptive case when the jjth 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ős–Rényi random graphs and graphs of bounded maximum degree.