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 is an element of V (G) belong to the ball of radius r around u?" with u is an element of V (G) and r <= R that is needed to determine v. We consider both the adaptive case when the jth 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 Erdos-Renyi random graphs and graphs of bounded maximum degree.