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 inspect an arbitrary set of $k$ vertices. The minimum $k$ for which the searcher can guarantee the capture of the intruder is called the inspection number of $G$. We also introduce and study the topological inspection number, a quantity that captures the limiting behavior of the inspection number under subdivisions of $G$. Our central theorem provides a full classification of graphs with topological inspection number up to $3$.
@article{10_37236_10577,
author = {Anton Bernshteyn and Eugene Lee},
title = {Searching for an intruder on graphs and their subdivisions},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {3},
doi = {10.37236/10577},
zbl = {1492.05099},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10577/}
}
TY - JOUR
AU - Anton Bernshteyn
AU - Eugene Lee
TI - Searching for an intruder on graphs and their subdivisions
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/10577/
DO - 10.37236/10577
ID - 10_37236_10577
ER -
%0 Journal Article
%A Anton Bernshteyn
%A Eugene Lee
%T Searching for an intruder on graphs and their subdivisions
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10577/
%R 10.37236/10577
%F 10_37236_10577
Anton Bernshteyn; Eugene Lee. Searching for an intruder on graphs and their subdivisions. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10577
