MIT PRIMES/Art of Problem Solving
CROWDMATH 2017: Graph Algorithms & Applications
No tags match your search
Mcop-and-killer
graph theory
Nowakowski
algorithm
Komarov
Dean
probability
cop-and-robber
cop-and-killer
Felsner
function
geometry
Blinovsky
Hartke
Nowakowski - Exercise A
calculus
geometric transformation
Komarov - Exercise C
Nowakowski - Exercise B
Problem 8
rectangle
rotation
3D geometry
analytic geometry
Blinovsky - Exercise A
Blinovsky - Exercise B
cop-and-pilferer
cop-vs-hypnostist
cop-vs-illusionist
Dean - Exercise A
derivative
Felsner - Exercise A
Hartke - Exercise A
integration
Komarov - Exercise B
magical opponents
parameterization
Problem 1
Problem 11
Problem 7
retract
Sawhney
Sawhney - Exercise A
set theory
tetrahedron
Thickness
No tags match your search
MG
Topic
First Poster
Last Poster
A procedure for finding winning strategies in cop-v-killer
rauss 1
N
Mar 9, 2018
by rauss
I've altered the procedure from Vertex-to-Vertex Pursuit in a Graph to model the cop-vs-killer game. I've attached a sketch of the definition and a python file modelling it for graphs represented as adjacency lists.
1 reply
Retracts and the Cop and Killer game
goodbear 7
N
Dec 26, 2017
by JGeneson
I have some additional results on the cop and killer game, with the intent of being able to characterize outcomes using retracts of the original graphs. Because I used some features of LaTeX not available on AoPS (such as defining some of the symbols I use), I'm just attaching the PDF here for now; if I have time later I'll convert to inline BBCode and update this post.
7 replies
Cop-and-killer game
cjquines0 96
N
Oct 16, 2017
by JGeneson
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.
Sketch
(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.
Sketch
(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.
Sketch
(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.
Sketch
Suppose the cop has picked a vertex, which we will root the tree at. The killer picks a vertex with distance two to the vertex the cop picked, which is possible as the tree is not a star. When the game begins, after each cop move, the killer moves toward the cop (there is only one possible move); thus the distance between them after this is still two, assuming the cop does not move backwards. The cop can only move forward for a finite number of moves as the graph does not contain a cycle, so eventually he will reach a leaf node. The cop then moves away from the leaf node, and is adjacent to the killer, after which the killer moves to the cop’s vertex and wins.
(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.
Sketch
For the former, the killer picks the opposite corner of the four-cycle and wins next turn. For the latter, killer picks vertex of distance two from cop, and moves so that they are never adjacent, neither player can win.
(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.
Sketch
For the former, killer chooses opposite corner of a four-cycle the cop is currently in. Killer mirrors cop's moves, maintaining distance two until cop is forced into corner, in which case killer wins next turn. For the latter, each player just maintains distance two from the other.
(Direct products don’t seem to have any connection, unlike cop-robber graphs.)
96 replies
No more topics!