? 2021 Elsevier B.V.We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The minimum number of probes necessary per round to locate the robber on a given graph G is the localization number ζ(G). In this paper, we improve the bounds for dense random graphs determining the asymptotic behaviour of ζ(G). Moreover, we extend the argument to sparse graphs.
Binomial random graphsCops and RobbersLocalization number
Dudek A.、English S.、Frieze A.、MacRury C.、Pralat P.
展开 >
Department of Mathematics Western Michigan University
Department of Mathematics University of Illinois Urbana-Champaign
Department of Mathematical Sciences Carnegie Mellon University
Department of Computer Science University of Toronto
NSTL
Elsevier
