Even flying cops should think ahead

01/22/2018
by   Anders Martinsson, et al.
0

We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to catch a robber in G, we show that the required number of cops can be much larger, even for graphs with small maximum degree. In particular, we show that there are 3-regular graphs where a linear number of cops are needed.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset