Journal of Combinatorics

Volume 7 (2016)

Number 4

Lazy Cops and Robbers played on random graphs and graphs on surfaces

Pages: 627 – 642

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n4.a4

Authors

Deepak Bal (Department of Mathematical Sciences, Montclair State University, Montclair, New Jersey, U.S.A.)

Anthony Bonato (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

William B. Kinnersley (Department of Mathematics, University of Rhode Island, Kingston, R.I., U.S.A.)

Paweł Prałat (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Abstract

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 Offner and Ojakian, 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.

Keywords

Cops and Robbers, vertex-pursuit games, random graphs, domination, adjacency property, graph genus

2010 Mathematics Subject Classification

05C57, 05C80

Full Text (PDF format)

Published 16 August 2016