math.CO cs.DM
Meyniel's conjecture on graphs of bounded degree. The game of Cops and Robbers is a well known pursuit evasion game played on graphs. It has been proved cite bounded degree that cubic graphs can have arbitrarily large cop number c(G) , but the known constructions show only that the set c(G) mid G text cubic is unbounded. In this paper we prove that there are arbitrarily large subcubic graphs G whose cop number is at least n 1 2 o(1) where n V(G) . We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weak Meyniel's conjecture for all graphs.