This topic is linked to Nowakowski.
Y by Adventure10
Consider the following generalization of the cop-and-robber game which is more symmetric. Our two players are now a cop and a killer, also a perfect information game. The cop picks a vertex and the killer also picks a vertex. Then the game begins, with the cop going first. He moves to an adjacent vertex, followed by the killer moving to an adjacent vertex. If after the cop moves he occupies the vertex the killer is located, he wins. Similarly, if after the killer moves, she occupies the vertex the cop is located, she wins. If neither happens after a finite amount of turns, it is a stalemate.
Some initial results.
Clearly all graphs with a universal vertex are cop-win.
All trees which are not stars are killer-win.
(A cop-win graph in the dismantlable sense is not always a cop-win graph in the cop-killer sense.)
Clearly the triangle is cop-win. Also, the four-cycle is killer-win. Cycles with more than five vertices are stalemate graphs.
(This is clearly different from the cop-robber game, in that the killer wins in the four-cycle.)
Grid graphs are killer-win, but king's graphs (with dimension at least two) are stalemate graphs.
(Direct products don’t seem to have any connection, unlike cop-robber graphs.)
Some initial results.
Clearly all graphs with a universal vertex are cop-win.
All trees which are not stars are killer-win.
(A cop-win graph in the dismantlable sense is not always a cop-win graph in the cop-killer sense.)
Clearly the triangle is cop-win. Also, the four-cycle is killer-win. Cycles with more than five vertices are stalemate graphs.
(This is clearly different from the cop-robber game, in that the killer wins in the four-cycle.)
Grid graphs are killer-win, but king's graphs (with dimension at least two) are stalemate graphs.
(Direct products don’t seem to have any connection, unlike cop-robber graphs.)