zbMATH — the first resource for mathematics

Lazy cops and robbers played on random graphs and graphs on surfaces. (English) Zbl 1350.05102
Summary: We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. The lazy cop number is the analogue of the usual cop number for this game. Lazy Cops and Robbers was recently introduced by D. Offner and K. Ojakian [Australas. J. Comb. 59, 229–250, (2014; Zbl 1296.05130)], who provided asymptotic upper and lower bounds on the analogue of the cop number of the hypercube. By investigating expansion properties, we provide asymptotically almost sure bounds on the lazy cop number of binomial random graphs \(\mathcal{G}(n,p)\) for a wide range of \(p=p(n)\). We provide an upper bound for the lazy cop number of graphs with genus \(g\) by using the Gilbert-Hutchinson-Tarjan separator theorem.

05C57 Games on graphs (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
Full Text: DOI