Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

G
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
rauss
Jan 16, 2018
rauss
Mar 9, 2018
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
goodbear
Nov 24, 2017
JGeneson
Dec 26, 2017
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.)
96 replies
cjquines0
Apr 23, 2017
JGeneson
Oct 16, 2017
No more topics!
a