A new bound for the cops and robbers problem

Details A new bound for the cops and robbers problem A new bound for the cops and robbers problem

2010-04-12

arxiv.org/abs/1004.2010v1

Mathematics

Combinatorics

4 pages

Scientific paper

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(\sqrt{n})$ cops are enough for any connected $G$ on $n$ vertices. Improving several previous results, we prove that the cop number of $n$-vertex graph is at most $n 2^{-(1+o(1))\sqrt{\log n}}$.

Affiliated with

Also associated with

No associations

Rating

A new bound for the cops and robbers problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A new bound for the cops and robbers problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new bound for the cops and robbers problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263153