1. A Bound for the Cops and Robbers Problem
- Author
-
Benny Sudakov and Alex Scott
- Subjects
Discrete mathematics ,Combinatorics ,General Mathematics ,Short paper ,Binary logarithm ,Graph ,Mathematics - Abstract
‡ Abstract. In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph G. Cops and a robber are allowed to move along the edges of G, and the goal of cops is to capture the robber. The cop number cðGÞ of G is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that Oð ffiffiffi p Þ cops are enough for any connected G on n vertices. Improving several previous results, we prove that the cop number of an n-vertex graph is at most n2 −ð1þoð1ÞÞ ffiffiffiffiffiffiffiffi log n p .A similar result independently and slightly before us was also obtained by Lu and Peng.
- Published
- 2011