Searching for an Intruder on Graphs and Their Subdivisions

Anton Bernshteyn, Eugene Lee

Published 2021-04-05Version 1

In this paper we analyze a variant of the pursuit-evasion game on a graph $G$ where the intruder occupies a vertex, is allowed to move to adjacent vertices or remain in place, and is 'invisible' to the searcher, meaning that the searcher operates with no knowledge of the position of the intruder. On each stage, the searcher is allowed to examine an arbitrary set of $k$ vertices. The minimum $k$ for which the searcher can guarantee the capture of the intruder is called the search number of $G$. We also introduce and study the topological search number, a quantity that captures the limiting behavior of the search number under subdivisions of $G$. Our central theorem provides a full classification of graphs with topological search number up to $3$.