We consider a game between two players on a connected graph. The first player is the cop and tries to catch the second player, who is the robber. In each round, the players can move to an adjacent vertex. If in any move the players are on the same vertex, the cop captures the robber and wins. If the robber cannot be captured in a finite number of moves, the robber wins. Graphs on which the cop always wins are called cop-win graphs, while those on which the robber always wins are called robber-win graphs. We characterize cop-win and robber-win graphs and describe a winning strategy for the cop. On cop-win graphs, we define the capture time as the smallest index of the round in which the cop is guaranteed to win. We find an upper bound for the capture time in general cop-win graphs and prove that it is the best upper bound. We also provide a better upper bound for the capture time for some families of graphs. We generalize the capture time problem to a game with one cop and multiple robbers. We find an upper bound and prove it to be the best for three robbers. We also find an upper bound for some families of graphs and prove it to be the best for trees.
|
