An Introduction to Lazy Cops and Robbers on Graphs. (1st November 2017)

• Record Type: Journal Article
• Authors: Sullivan, Brendan W.; Townsend, Nikolas; Werzanski, Mikayla L.
• Is Part Of: College mathematics journal. Volume 48:Number 5(2017)
• Page Start: 322
• Page End: 333
• Publication Date: 2017-11-01
• Subjects: Mathematics -- Study and teaching -- Periodicals; Mathematics -- Periodicals; Mathematics; Mathematics -- Study and teaching; Periodicals; 510.071
• DOI: 10.4169/college.math.j.48.5.322
• Languages: English
• ISSNs: 0746-8342

Abstract

Summary: Cops and Robbers is a classic pursuit—evasion game played on graphs. A new variant, Lazy Cops and Robbers, allows only one cop to move at a time, making the game's mechanics more akin to chess. We investigate and describe a few examples, showing that on some graphs lazy cops can be as effective as ordinary cops, but on other graphs they are not (and sometimes they are much worse). Some examples are based on the cops and robber moving like particular chess pieces. We also mention related results and pose some open problems.