Lazy Cops and Robbers on Hypercubes

Deepak Bal, Anthony Bonato, William B. Kinnersley, PaweŁ PraŁat

Research output: Contribution to journalArticle

10 Citations (Scopus)

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. 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.

Original languageEnglish
Pages (from-to)829-837
Number of pages9
JournalCombinatorics Probability and Computing
Volume24
Issue number6
DOIs
StatePublished - 1 Nov 2015

Fingerprint

Hypercube
Game
Probabilistic Methods
Potential Function
Upper and Lower Bounds
Lower bound
Analogue

Cite this

Bal, Deepak ; Bonato, Anthony ; Kinnersley, William B. ; PraŁat, PaweŁ. / Lazy Cops and Robbers on Hypercubes. In: Combinatorics Probability and Computing. 2015 ; Vol. 24, No. 6. pp. 829-837.
@article{1c114fef799047a6bd6a6dc5759e5b64,
title = "Lazy Cops and Robbers on Hypercubes",
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. 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.",
author = "Deepak Bal and Anthony Bonato and Kinnersley, {William B.} and PaweŁ PraŁat",
year = "2015",
month = "11",
day = "1",
doi = "10.1017/S0963548314000807",
language = "English",
volume = "24",
pages = "829--837",
journal = "Combinatorics Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "6",

}

Bal, D, Bonato, A, Kinnersley, WB & PraŁat, P 2015, 'Lazy Cops and Robbers on Hypercubes', Combinatorics Probability and Computing, vol. 24, no. 6, pp. 829-837. https://doi.org/10.1017/S0963548314000807

Lazy Cops and Robbers on Hypercubes. / Bal, Deepak; Bonato, Anthony; Kinnersley, William B.; PraŁat, PaweŁ.

In: Combinatorics Probability and Computing, Vol. 24, No. 6, 01.11.2015, p. 829-837.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Lazy Cops and Robbers on Hypercubes

AU - Bal, Deepak

AU - Bonato, Anthony

AU - Kinnersley, William B.

AU - PraŁat, PaweŁ

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

VL - 24

SP - 829

EP - 837

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 6

ER -