Even flying cops should think ahead

DOI10.1007/978-3-319-96151-4_28MaRDI QIDQ1661906zbMATH OpenOpenAlexFDO

Authors Anders Martinsson, Florian Meier, Patrick Schnider, Angelika Steger

Publication date 17 August 2018

Full work available at URL https://arxiv.org/abs/1801.07193

zbMATH Keywords

cops and robbersentanglement gameprobabilistic method

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: 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.

Recommendations

• Note on a pursuit game played on graphs
• Cops and robbers in a random graph
• A game of cops and robbers
• Cops and robbers playing on edges
• scientific article; zbMATH DE number 5241699

Cited in

(1)

• Advice to the relevantist policeman

This page was built for publication: Even flying cops should think ahead

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661906)