Cops and robbers on Cayley graphs and embedded graphs

We consider the game of cops and robbers, which is a game played on a finite graph G by two players, Alice and Bob. Alice controls a team of cops, and Bob controls a robber, both of which occupy vertices of G. On Alice's turn, she may move each cop to an adjacent vertex or leave it at its current position. Similarly, on Bob's turn, he may move the robber to an adjacent vertex or leave it at its current position. Traditionally, Alice wins the game when a cop occupies the same vertex as the robber---that is, when a cop captures the robber. Conversely, Bob wins the game by letting the robber avoid capture forever. In a variation of the game, Alice wins the game when each neighbor of the robber's vertex is occupied by a cop---that is, when cops surround the robber. We will consider both of these winning conditions. The most fundamental graph invariant with regard to the game of cops and robbers is the cop number of a graph G, which denotes the minimum number of cops that Alice needs in order to have a winning strategy on G. We will introduce new techniques that may be used to calculate lower and upper bounds for the cop numbers of certain Cayley graphs. In particular, we will show that the well-known Meyniel's conjecture holds for both undirected and directed abelian Cayley graphs. We will also introduce new techniques for establishing upper bounds on the cop numbers of surface-embedded graphs bounded by the genus of the surface in the surrounding win condition.