Journal of Combinatorics

Volume 5 (2014)

Number 1

Cops and Robbers playing on edges

Pages: 131 – 153

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n1.a6

Authors

Andrzej Dudek (Department of Mathematics, Western Michigan University, Kalamazoo, Mich., U.S.A.)

Przemysław Gordinowicz (Institute of Mathematics, Technical University of Łódź, Poland)

Paweł Prałat (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Abstract

In the game of cops and robbers, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$. In this paper, we consider the variant of the game in which both players play on edges instead of vertices, yielding the edge cop number. We relate the new graph parameter to the classic one, investigate Meyniel extremal families, and characterize edge copwin graphs. We also play the game on random graphs and planar graphs.

Full Text (PDF format)