Cops and Robber on Cartesian products and some classes of hypergraphs

Pinkaew Siriwong, Ratinan Boonklurb, Henry Liu, Sirirat Singhun

Published 2021-07-25Version 1

The game of Cops and Robber is a pursuit-evasion game which is usually played on a connected graph. In the game, a set of cops and a robber move around the vertices of a graph along edges, where the cops aim to capture the robber, while the robber aims to avoid capture. Much research about this game have been done since the early 1980s. The game has a natural generalisation to being played on connected hypergraphs, where the cops and the robber may now move along hyperedges. In this paper, we shall provide a characterisation of all hypergraphs where one cop is sufficient to capture the robber. The cop-number of a connected hypergraph is the minimum number of cops required in order to capture the robber. We shall prove some results about the cop-number of certain hypergraphs, including hypertrees and Cartesian products of hypergraphs.