A Bound for the Cops and Robbers Problem
Alex Scott, Benny Sudakov · SIAM Journal on Discrete Mathematics · 2011
In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph [Formula: see text]. Cops and a robber are allowed to move along the edges of [Formula: see text], and the goal of cops is to capture the robber. The cop number [Formula: see text] of [Formula: see text] is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that [Formula: see text] cops are enough for any connected [Formula: see text] on [Formula: see text] vertices. Improving several previous results, we prove that the cop number of an [Formula: see text]-vertex graph is at most [Formula: see text]. A similar result independently and slightly before us was also obtained by Lu and Peng.