Even flying cops should think ahead
2018
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.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
8
References
0
Citations
NaN
KQI