TY - JOUR
T1 - Lazy Cops and Robbers on Hypercubes
AU - Bal, Deepak
AU - Bonato, Anthony
AU - Kinnersley, William B.
AU - PraŁat, PaweŁ
N1 - Publisher Copyright:
Copyright © Cambridge University Press 2015.
PY - 2015/11/1
Y1 - 2015/11/1
N2 - 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. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by Offner and Ojakian, who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By coupling the probabilistic method with a potential function argument, we improve on the existing lower bounds for the lazy cop number of hypercubes.
AB - 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. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by Offner and Ojakian, who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By coupling the probabilistic method with a potential function argument, we improve on the existing lower bounds for the lazy cop number of hypercubes.
UR - http://www.scopus.com/inward/record.url?scp=84944514383&partnerID=8YFLogxK
U2 - 10.1017/S0963548314000807
DO - 10.1017/S0963548314000807
M3 - Article
AN - SCOPUS:84944514383
SN - 0963-5483
VL - 24
SP - 829
EP - 837
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 6
ER -