Cops and Robbers Game on the Cartesian, Direct and Strong Products of Hypergraphs

Pinkaew Siriwong, Ratinan Boonklurb, Sirirat Singhun

Abstract

The game of cops and robbers is a game that is usually played on a finite connected graphG with two players, cop and robber, according to the following rules: (i) cop chooses a vertex of G to begin and robber then chooses other vertex of G to begin and (ii) they alternatively move from their present vertices to adjacent vertices along edges of G where the first move is a turn of cop. However, they can also choose not to move from their positions at each of their turns as well. If cop catches some robber after finite moves by occupying the same vertex as robber, it is called cop wins and such a graph is called a cop-win graph; otherwise, it is called robber wins and such a graph is called a robber-win graph. Recently, the game of cops and robbers played on a hypergraph has been defined and some rules of the game have been changed; that is, they can move from their present vertex x to any vertex y which is in the same hyperedge as vertex x. A hypergraph which cop wins is called a cop-win hypergraph; otherwise, a robber-win hypergraph. Throughout this paper, we consider the game of cops and robbers on the products of cop-win hypergraphs. Then, we prove that their cartesian and minimal (maximal) rank preserving direct products are robber-win hypergraphs, and their standard (normal) strong product is still a cop-win hypergraph.