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

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

a
p
Visibility Graphs J
Cop-and-killer game
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cjquines0
510 posts
#1 • 1 Y
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.
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.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#2 • 2 Y
Y by Adventure10, Mango247
cjquines0 wrote:
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.)
This is a nice generalization of the cop-and-robber game, and these are excellent results so far. Is it possible to classify which bipartite graphs are cop-win, killer-win, or stalemate?
Also, is it possible to classify all graphs with at most $n$ vertices for some small $n$?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cjquines0
510 posts
#3 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
This is a nice generalization of the cop-and-robber game, and these are excellent results so far. Is it possible to classify which bipartite graphs are cop-win, killer-win, or stalemate?
Also, is it possible to classify all graphs with at most $n$ vertices for some small $n$?

Well, a bipartite graph is cop-win iff it is the claw. Sufficiency is vacuous, for necessity suppose it were not the claw, the killer merely picks any vertex in the same set the cop picks. At the start of each of the cop’s turns the killer is in the same set he is, so he can never catch her.

We can classify $n \leq 4$ easily, but $n = 5$ seems to be harder:
http://i.imgur.com/yGO9VRQ.png
(left: stalemate; middle: cop-win, cop picks top vertex; right: killer-win)

Might be wrong: cactus graphs with a cycle with at least five vertices are stalemate. Otherwise, if they are not the star, they are killer-win.
Sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#4 • 2 Y
Y by Adventure10, Mango247
cjquines0 wrote:
JGeneson wrote:
This is a nice generalization of the cop-and-robber game, and these are excellent results so far. Is it possible to classify which bipartite graphs are cop-win, killer-win, or stalemate?
Also, is it possible to classify all graphs with at most $n$ vertices for some small $n$?
Well, a bipartite graph is cop-win iff it is the claw. Sufficiency is vacuous, for necessity suppose it were not the claw, the killer merely picks any vertex in the same set the cop picks. At the start of each of the cop’s turns the killer is in the same set he is, so he can never catch her.
The claw is the star with $4$ total vertices, right?
Are $n$-vertex stars cop-win for all $n$?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#5 • 2 Y
Y by Adventure10, Mango247
cjquines0 wrote:
Might be wrong: cactus graphs with a cycle with at least five vertices are stalemate. Otherwise, if they are not the star, they are killer-win.
Sketch
This is a great idea. Does anyone see how to fill in the details to turn this into a proof?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#6 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
cjquines0 wrote:
Might be wrong: cactus graphs with a cycle with at least five vertices are stalemate. Otherwise, if they are not the star, they are killer-win.
Sketch
This is a great idea. Does anyone see how to fill in the details to turn this into a proof?

Hmmm... here are two counterexamples. Neither have any 5-cycles, and neither is killer win.

Here is a cop (1st player) win. Cop picks one of the vertices of the center triangle. No matter where killer goes, cop can chase him into a corner.
[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(10,12)--(10,10)--(12,10)--cycle);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]

Here is a similar one, but this one is a stalemate. As before, the cop picks a vertex of either triangle, the killer pics a vertex of the other. The killer can't lose in his triangle, and the cop can't lose in hers. (One can chase the other, but is quickly chased back to their original triangle).

[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(12,12)--cycle);
draw((10,12)--(12,12)--(10,10)--cycle, blue);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]

Let $G$ be a cactus graph, and consider the following 3 statements:
  1. $G$ contains a cycle of at least 5 vertices
  2. $G$ contains two disjoint cycles of 3 vertices
  3. $G$ contains at least one cycle of 3 vertices.

I claim that:
  1. Cop wins iff 1. and 2. are false and 3. is true.
  2. There is a stalemate iff 1. is true and/or 2. is true.
  3. Killer wins iff all statements above are false.

(Due to the lateness of the hour, I will postpone the proof of the above for another day. :sleep2:)
This post has been edited 2 times. Last edited by goodbear, Apr 29, 2017, 7:45 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cjquines0
510 posts
#7 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
The claw is the star with $4$ total vertices, right?
Are $n$-vertex stars cop-win for all $n$?

I meant star, not claw, sorry.
goodbear wrote:
Let $G$ be a cactus graph, and consider the following 3 statements:
  1. $G$ contains a cycle of at least 5 vertices
  2. $G$ contains two disjoint cycles of 3 vertices
  3. $G$ contains at least one cycle of 3 vertices.

I claim that:
  1. Cop wins iff 1. and 2. are false and 3. is true.
  2. There is a stalemate iff 1. is true and/or 2. is true.
  3. Killer wins iff all statements above are false.

I was waiting for you to reply :) This is a great result. Perhaps it can be applied to the original cop-robber problem to get a new characterization?

Here are some observations I made today, both inspired by Nowakowski’s results:

Cop-win, killer-win and stalemate graphs are all non-retract-closed. $C_4$ retracts to $P_3$, the former is killer-win and the latter is cop-win. Also $C_6$, stalemate, retracts to $P_4$. Products also don’t seem to help much as our graphs are non-reflexive unlike Nowakowski – if not moving on a turn was allowed, then all games would end with a stalemate. However, we can still get a homomorphism-related result:

A graph homomorphic to a graph such that each image has at least two distinct vertices in its pre-image is non-cop-win. Sketch
(are there other results based on homomorphisms? perhaps we can get a result based on graph products, but probably not as strong as nowakowski’s result on cop-robber graphs)

Also inspired by Nowakowski, we can do something like dismantling. Say vertex $u$ covers a vertex $v$ if $N(v) \subseteq N(u)$. We have the following result. (Note that this condition is not sufficient: join a $C_5$ and a $C_4$ with a bridge.)

A graph is a non-stalemate graph only if it has a universal vertex or one vertex covers another. Sketch
(perhaps we can extend this idea to get a dismantling order? i can’t figure this out – one idea is to consider the graph with the same vertices, except replace the edges with directed edges representing covering. then trace a path or something, i couldn’t get this to work.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#8 • 1 Y
Y by Adventure10
goodbear wrote:
Let $G$ be a cactus graph, and consider the following 3 statements:
  1. $G$ contains a cycle of at least 5 vertices
  2. $G$ contains two disjoint cycles of 3 vertices
  3. $G$ contains at least one cycle of 3 vertices.

I claim that:
  1. Cop wins iff 1. and 2. are false and 3. is true.
  2. There is a stalemate iff 1. is true and/or 2. is true.
  3. Killer wins iff all statements above are false.

(Due to the lateness of the hour, I will postpone the proof of the above for another day. :sleep2:)

(Assuming $G$ is not a star.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#9 • 1 Y
Y by Adventure10
goodbear wrote:
goodbear wrote:
Let $G$ be a cactus graph, and consider the following 3 statements:
  1. $G$ contains a cycle of at least 5 vertices
  2. $G$ contains two disjoint cycles of 3 vertices
  3. $G$ contains at least one cycle of 3 vertices.

I claim that:
  1. Cop wins iff 1. and 2. are false and 3. is true.
  2. There is a stalemate iff 1. is true and/or 2. is true.
  3. Killer wins iff all statements above are false.

(Due to the lateness of the hour, I will postpone the proof of the above for another day. :sleep2:)

(Assuming $G$ is not a star.)
This result seems very nice. Is there a proof?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#10 • 1 Y
Y by Adventure10
goodbear wrote:
Hmmm... here are two counterexamples. Neither have any 5-cycles, and neither is killer win.

Here is a cop (1st player) win. Cop picks one of the vertices of the center triangle. No matter where killer goes, cop can chase him into a corner.
[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(10,12)--(10,10)--(12,10)--cycle);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]
What happens if the cop starts at the bottom left vertex of the triangle and the killer starts at the top vertex of the leftmost diamond?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#11 • 2 Y
Y by Adventure10, Mango247
cjquines0 wrote:
A graph homomorphic to a graph such that each image has at least two distinct vertices in its pre-image is non-cop-win. Sketch
(are there other results based on homomorphisms? perhaps we can get a result based on graph products, but probably not as strong as nowakowski’s result on cop-robber graphs)
The new results above are excellent. Any conjectures about a result based on graph products?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#12 • 1 Y
Y by Adventure10
JGeneson wrote:
goodbear wrote:
Hmmm... here are two counterexamples. Neither have any 5-cycles, and neither is killer win.

Here is a cop (1st player) win. Cop picks one of the vertices of the center triangle. No matter where killer goes, cop can chase him into a corner.
[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(10,12)--(10,10)--(12,10)--cycle);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]
What happens if the cop starts at the bottom left vertex of the triangle and the killer starts at the top vertex of the leftmost diamond?

The cop goes around the triangle, then chases the killer. She (the cop) will win.
This post has been edited 2 times. Last edited by goodbear, May 1, 2017, 2:26 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JGeneson
1096 posts
#13 • 2 Y
Y by Adventure10, Mango247
goodbear wrote:
JGeneson wrote:
goodbear wrote:
Hmmm... here are two counterexamples. Neither have any 5-cycles, and neither is killer win.

Here is a cop (1st player) win. Cop picks one of the vertices of the center triangle. No matter where killer goes, cop can chase him into a corner.
[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(10,12)--(10,10)--(12,10)--cycle);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]
What happens if the cop starts at the bottom left vertex of the triangle and the killer starts at the top vertex of the leftmost diamond?

The cop goes around the triangle, then chases the killer. She (the cop) will win.
Let's call the leftmost diamond L.
Can't the killer move back and forth between the top vertex and the rightmost vertex of L?
If the cop moves from the triangle to the rightmost vertex of L, the killer will be at the top vertex of L and can defeat the cop on their next turn. How can the cop handle this situation?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#14 • 2 Y
Y by Adventure10, Mango247
JGeneson wrote:
goodbear wrote:
JGeneson wrote:
What happens if the cop starts at the bottom left vertex of the triangle and the killer starts at the top vertex of the leftmost diamond?

The cop goes around the triangle, then chases the killer. She (the cop) will win.
Let's call the leftmost diamond L.
Can't the killer move back and forth between the top vertex and the rightmost vertex of L?
If the cop moves from the triangle to the rightmost vertex of L, the killer will be at the top vertex of L and can defeat the cop on their next turn. How can the cop handle this situation?

[asy]
draw((3,13)--(6,13)--(6,10)--(3,10)--cycle);
draw((12,14)--(14,14)--(14,12)--(10,12)--(10,10)--(12,10)--cycle);
draw((6,10)--(8,7)--(10,10));
draw((8,7)--(10,4)--(6,4)--cycle, blue);
label("$u$",(6,4),SW);
label("$v$",(10,4),ESE);
label("$w$",(8,7),E);
draw((3,10)--(5,8));
draw((10,10)--(14,10)--(14,8));
draw((0,6)--(2,7)--(4,6)--(2,5)--cycle);
label("$L$",(2,6));
draw((4,6)--(6,4));
draw((12,8)--(12,6)--(14,6));
draw((10,4)--(12,6));
draw((10,4)--(11,2)--(10,0)--(9,2)--cycle);
draw((11,2)--(13,2));
draw((13,2)--(14,4)--(15,2)--(14,0)--cycle);
[/asy]

In your scenario, the cop moves from $u$ to $v$ to $w$ then back to $u.$ If the killer had attempted to move to $u$ during any of those moves, the cop would immediately capture him. If not, the cop will get him now, by moving to the rightmost vertex of $L,$ cornering or capturing the killer.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#15 • 1 Y
Y by Adventure10
JGeneson wrote:
goodbear wrote:
goodbear wrote:
Let $G$ be a cactus graph, and consider the following 3 statements:
  1. $G$ contains a cycle of at least 5 vertices
  2. $G$ contains two disjoint cycles of 3 vertices
  3. $G$ contains at least one cycle of 3 vertices.

I claim that:
  1. Cop wins iff 1. and 2. are false and 3. is true.
  2. There is a stalemate iff 1. is true and/or 2. is true.
  3. Killer wins iff all statements above are false.

(Due to the lateness of the hour, I will postpone the proof of the above for another day. :sleep2:)

(Assuming $G$ is not a star.)
This result seems very nice. Is there a proof?

Claim a: Cop wins if 1. and 2. are false, and 3. is true.

Proof:
Since $G$ is a cactus graph and has no disjoint triangles, there is a vertex $v$ that is contained in all its triangles. As illustrated below, color this vertex red, and the other two vertices in each triangle yellow and blue, respectively. Now color all remaining vertices with the complimentary color of its neighbor: Green borders red, orange borders blue, purple borders yellow, and vice versa.
[asy]
unitsize(0.5cm);
draw((4,7)--(5,8)--(5,9)--(4,9)--(4,4)--(5,6));
draw((2,4)--(2,5)--(4,6)--(5,6)--(6,5)--(7,5));
draw((4,4)--(3,2)--(3,4)--cycle);
draw((4,4)--(6,3)--(4,3)--cycle);
draw((6,3)--(7,2)--(6,1)--(5,2)--cycle);
draw((6,1)--(6,0)--(7,0));
draw((3,2)--(2,1)--(1,2)--(2,3)--cycle);
draw((1,2)--(0,2)--(0,1));
draw((4,4)--(14,2)); // leash
draw((10,2.5)--(11,2));
draw((11,2)--(14,2)--(14,1)--(12,1)--cycle);
draw((11,0.5)--(12,0.5)--(12,1)--(12.5,0.5)--(12,0));
draw((13.5,0)--(14,0.5)--(14,1)--(15,1)--(15,0.5));
draw((13.5,3.5)--(14,3));
draw((14,3)--(15,3)--(16,2)--(14,2)--cycle);
dot((4,4), red);  // center
dot((3,4), yellow); // left leg
dot((3,2), blue);
dot((2,3), orange);
dot((2,1), orange);
dot((1,2), blue);
dot((0,2), orange);
dot((0,1), blue);
dot((4,3), yellow); // right leg
dot((6,3), blue);
dot((5,2), orange);
dot((7,2), orange);
dot((6,1), blue);
dot((6,0), orange);
dot((7,0), blue);
dot((5,6), yellow); // body
dot((4,6), blue);
dot((2,5), orange);
dot((2,4), blue);
dot((6,5), purple);
dot((7,5), yellow);
dot((4,7), orange); // head
dot((5,8), blue);
dot((5,9), orange);
dot((4,9), blue);
dot((14,2), green); // dog's neck
dot((14,3), red); // dog's head
dot((13.5,3.5), green);
dot((15,3), green);
dot((16,2), red);
dot((14,1), red); // dog's body
dot((12,1), green);
dot((11,2), red);
dot((10,2.5), green); // tail tip
dot((12,0.5), red);
dot((11,0.5), green);
dot((12.5,0.5), red);
dot((12,0), green);
dot((14,0.5), green);
dot((13.5,0), red);
dot((15,1), red);
dot((15,0.5), green);
[/asy]
The cop starts out at $v.$ We have 4 initial cases:
  • If the killer is at a yellow or orange vertex, the cop moves to an adjacent yellow vertex.
  • If the killer is at a blue or purple vertex, the cop moves to an adjacent blue vertex.
  • If the killer is at a green vertex, the cop moves towards him.
  • If the killer is at a red vertex, the cop moves around one of the triangles (red to yellow to blue, then back to red); by the time she gets back to $v,$ the killer will be at a green vertex.
The remainder of the cop's turns are always towards the killer, whom she will corner. The cop cannot be killed because the killer always moves to a vertex that's not colored the same as the cop's. The cop will win because the killer will be forced away from the cop, until he meets a dead end.

Claim b, Part 1: Stalemate if statement 1. is true.

Proof:
[asy]
unitsize(0.5cm);
draw((2,8)--(3,8)--(3,7)--(2,6)--cycle);
draw((2,6)--(3,6)--(2,5)--cycle);
draw((2,5)--(2,2)--(4,3)--(3.5,1));
draw((3,6)--(4,5)--(6,5.5)--(6,6)--(5,5.25));
draw((6,5.5)--(6.25,5.25));
draw((3,6)--(4,4.5)--(5.5,4.5)--(6,5));
draw((6,5)--(6.6,5)--(6.5,4.5)--(6.1,4.5)--cycle);
draw((0,0)--(9,0));
draw((5,0)--(5,3)--(4,4)--(9,4)--(8,3)--(8,0)--cycle, blue+1.5);
draw((1,2)--(1,6)--(1.5,6)--(1,4));
draw((1,0)--(1,2)--(3,2)--(3,0)--cycle, blue+1.5);
[/asy]
Cop cannot lose if she starts in the $n \ge 5$-cycle. Likewise for the killer, so long as he does not start next to the cop. This is because $G$ is a cactus graph, so the cop and the killer are always adjacent to a vertex in the $n$-cycle that is not adjacent to the other.


Claim b, Part 2: Stalemate if 2. is true.

Proof:
[asy]
unitsize(0.5cm);

draw((6,11)--(7,10)--(6,9)--(5,10)--cycle); // head
draw((5,11)--(5,10));
draw((7,11)--(7,10));
draw((6,12)--(6,10));

draw((-2,11)--(-1,10)--(-2,9)--(-3,10)--cycle); // left arm
draw((2,11)--(3,10)--(2,9)--(1,10)--cycle);
draw((-1,10)--(1,10));
draw((0,10)--(2,8)--(0,8)--cycle, blue+1.5);
draw((2,8)--(3,9)--(5,9)--(3,6)--cycle);

draw((14,11)--(15,10)--(14,9)--(13,10)--cycle); // Right arm
draw((10,11)--(11,10)--(10,9)--(9,10)--cycle);
draw((13,10)--(11,10));
draw((12,10)--(12,8)--(10,8)--cycle, blue+1.5);
draw((10,8)--(9,9)--(7,9)--(9,6)--cycle);

draw((5,9)--(7,9)); // Shoulder

draw((6,9)--(6,8));
draw((6,8)--(7,7)--(6,6)--(5,7)--cycle);
draw((2,5)--(10,5));
draw((4,5)--(6,6)--(8,5)--cycle,blue+1.5);
draw((2,5)--(2,2));
draw((2.5,5)--(2.5,2));
draw((10,5)--(10,2));
draw((9.5,5)--(9.5,2));
draw((4,5)--(5,4)--(4,3)--(3,4)--cycle);
draw((8,5)--(9,4)--(8,3)--(7,4)--cycle);
draw((4,3)--(5,1)--(3,1)--cycle,blue+1.5);
draw((8,3)--(9,1)--(7,1)--cycle,blue+1.5);
draw((5,1)--(5,0)--(3,0));
draw((7,1)--(7,0)--(9,0));
[/asy]
Cop cannot lose if she chooses a vertex in one of the triangles. Likewise for the killer, so long as he does not do so in a triangle that the cop is in. This is because $G$ is a cactus graph, so the cop and the killer are always adjacent to a vertex in the $3$-cycle that is not adjacent to the other.


Claim c: Killer wins if all statements above are false.

Proof:
Since all statements above are false, this is a bipartite graph. Accordingly, color the vertices blue and orange such that no two neighbors have the same color.
[asy]
unitsize(0.5cm);
draw((2,9)--(2,8));
draw((3,10)--(3,9));
draw((4,9)--(4,8));
draw((3,9)--(4,8)--(3,7)--(2,8)--cycle);
draw((0,5)--(0,6)--(1,6));
draw((5,6)--(6,6)--(6,7));
draw((1,6)--(2,7)--(4,5)--(5,6)--(4,7)--(2,5)--cycle);
draw((3,7)--(3,4));
draw((1,3)--(3,4)--(5,3));
draw((1,3)--(2,2)--(1,1)--(0,2)--cycle);
draw((5,3)--(6,2)--(5,1)--(4,2)--cycle);
draw((1,1)--(1,0)--(0,0));
draw((5,1)--(5,0)--(6,0));
dot((3,10), orange);
dot((2,9), blue);
dot((4,9), blue);
dot((3,9), blue);
dot((2,8), orange);
dot((4,8), orange);
dot((3,7), blue);
dot((3,6), orange);
dot((2,7), blue);
dot((1,6), orange);
dot((0,6), blue);
dot((0,5), orange);
dot((2,5), blue);
dot((4,7), blue);
dot((5,6), orange);
dot((6,6), blue);
dot((6,7), orange);
dot((4,5), blue);
dot((3,4), blue);
dot((1,3), orange);
dot((0,2), blue);
dot((2,2), blue);
dot((1,1), orange);
dot((1,0), blue);
dot((0,0), orange);
dot((5,3), orange);
dot((4,2), blue);
dot((6,2), blue);
dot((5,1), orange);
dot((5,0), blue);
dot((6,0), orange);
[/asy]
After the cop has chosen a vertex, the killer choses one of the same color.

The remainder of the killer's turns are always towards the cop, whom he will corner. The killer cannot be captured because the cop always moves to a vertex that's not colored the same as the killer's. The killer will win because the cop will be forced away from the killer, until she meets a dead end. Literally.

We now build a truth table to ensure that we have covered all cases, thereby proving the "only if" part of each case. We note that statement 2. implies 3.

$$\begin{array}{ccc|c} 
\text{1} & \text{2} & \text{3} & \text{Winner} \\ \hline
\text{T} & \text{T} & \text{T} & \text{stalemate} \\
\text{T} & \text{T} & \text{F} & \text{N/A} \\
\text{T} & \text{F} & \text{T} & \text{stalemate} \\
\text{T} & \text{F} & \text{F} & \text{stalemate} \\
\text{F} & \text{T} & \text{T} & \text{stalemate} \\
\text{F} & \text{T} & \text{F} & \text{N/A} \\
\text{F} & \text{F} & \text{T} & \text{cop} \\
\text{F} & \text{F} & \text{F} & \text{killer} \\
\end{array}$$
Since we covered all cases, the "only if" claim holds in each case.
This post has been edited 1 time. Last edited by goodbear, May 1, 2017, 4:33 AM
Z K Y
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
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
J
H
Generalizations for Vertex-to-Vertex Pursuit on Graph
Zion17STEM21   32
N Jan 24, 2017 by abk2015
I am interested in exploring generalizations for this problem.

Some of my ideas are:
1. Continuous version: they could meet at any point on the graph itself, assume uniform speed.
2. The cop and the robber may have different speeds.
3. Combining both 1.) and 2.)

One way where the problem does not resemble real life is when the robber chooses after the cop has chosen. In a city there may be many cops, and which cop (or team of cops) is deployed to chase after the robber may depend on the robber's position.
32 replies
Zion17STEM21
Jan 5, 2017
abk2015
Jan 24, 2017
J
H
Some Ideas About This Problem
M5_1792   5
N Jan 24, 2017 by abk2015
One thing I noticed is that the definition of winning is unevenly defined for the cop and the robber; in the paper the cop wins if he is able to capture the robber in a finite number of steps while the robber wins if he is able to evade the cop infinitely.

To change this I think that there must be some positive integer \(t\) which should be taken as the number of moves the cop and the robber each get while playing the game. Thus, in this modified version of the game the cop wins if he captures the robber in \(t\) moves while the robber wins if he evades the cop in \(t\) moves.

I apologize if this has already been written somewhere.
5 replies
M5_1792
Jan 16, 2017
abk2015
Jan 24, 2017
J
H
Further Generalizations for Vertex-to-vertex Pursuit
adamodoherty   15
N Jan 17, 2017 by JGeneson
Thanks Silverbach for adding some very interesting ways to make this more realistic. I will be looking for further ways to make this situation as applicable to real life as possible. Here are my ideas:

My first idea is rather simple but will obviously make this much more realistic and it is to add multiple cops (I'm not sure if somebody has already suggested this). With multiple cops we can better simulate what a full police force would do when actually chasing a real-life robber. These cops could have individual tactics to create a better overall strategies. The addition of multiple cops adds some interesting scenarios and some interesting questions for what these cops can do. Here is what I was thinking. Cops are able to communicate with each other about their positions and are able to communicate the position of the gambler if they get within n vertices of the gambler (assuming that there are no turns which would obstruct vision between the cop and the gambler). Obviously, then the other cop could alter his strategy to minimize capture time. Once a cop is looked in the cop could be able to follow the gambler (look to my second paragraph more on this). Furthermore cops could set up blockades on certain strategic vertices if this minimizes capture time.

I also think to make this more realistic we need to add in a probability distribution for each vertex. This probability distribution would not control the movement of the cop as in Komarov and Winkler but rather probability of either

A). Stoppage or
B). Delay

With the probability of stoppage being the probability that a car crashes resulting in the stoppage of that particular player (resulting in either the capture of gambler or the total stoppage of one cop) and the probability of delay denoting the probability of some delay of n moves at a certain position which could result in capture for gambler or perhaps losing sight of gambler for cop. These would simulate the real scenario of crashing and the scenario of getting stuck in traffic or further non-natural (and non-permanent) dead ends.

I also like the idea of multigraphs with two-colored edges as they can be used quite easily to represent either different routes (one of which is forbidden for gambler) or can be parallel edges representing more or less lanes of traffic in which either the cop or the gambler can move between.

Lastly I would like to further the idea of creating "dead nodes" to include both nodes which the cop touches and nodes which the gambler touches as it seems to me to be unlikely that any real life "node" would be able to be reoccupied but rather much more likely that the pursuit would continue on staying away from previously occupied spaces.

Anyway, I haven't worked on these generalizations or their effects much but I think all the generalizations I note (especially the multiple cops and addition of the probability distribution) will make this game much more similar to what actually occurs in real life cop robber chases. Tell me what you think.


15 replies
adamodoherty
Jan 10, 2017
JGeneson
Jan 17, 2017
J
H
Cop-win graphs based on number of edges
cjquines0   19
N Jan 13, 2017 by goodbear
Idea: intuitively, the more edges a graph has, the easier it is for the cop to win.

Let $f(n)$ be the largest number such that there is all graphs with $n$ vertices and at least $f(n)$ edges are cop-win.

On the upper bound, for example, $K_n$ is easily a cop-win graph. We can go further: a graph with $n$ vertices that has a vertex of degree $n-1$ is also a cop-win graph. (Here and for the rest of this post I will not count loops.) Thus, any graph which has at least $\frac{n(n-2)}{2} + 1$ edges is cop-win, so we get the straightforward bound $$f(n) \leq \frac{n(n-2)}{2} + 1.$$
For the lower bound, here is a construction of a robber-win graph with lots of edges. The idea is to use Nowakowski’s Corollary from Theorem 1: use the direct product of $C_4$ and $P_k$, giving a graph with $4k$ vertices and $8k^2 - 8k + 4$ edges. Thus $$f(n) \geq \frac{n^2 - 4n + 8}{2} + 1.$$
These aren’t very good bounds, but they kinda sorta work. Does this look like a good way to characterize cop-robber graphs, or should we try something else?
19 replies
cjquines0
Jan 6, 2017
goodbear
Jan 13, 2017
J
H
Some Generalizations of Vertex-to-Vertex Pursuit
Silverbach   6
N Jan 13, 2017 by cjquines0
The first thing that comes to my mind is playing the game on directed graphs. That is, instead of there only being an edge between nodes on the graph, there are edges with arrows pointing toward one node, the other node, or both. This is analagous to how the real world has some one-way streets as well as some two-way streets (instead of just having two-way streets).

Another generalization would be to have a weighted graph. That is, a graph where each node has a number associated with it. The number could represent the number of turns the other player gets after a player goes to the node. The non-generalized version would be the equivalent of every node having a value of 1, because every player only gets to play 1 turn at a time. But with a weighted graph, if a node has 2 on it, then the other player makes two moves. Or, you could even have a node with 0, meaning the player instantly goes again. Nodes with negative numbers could revert the other players last move(s). But, that may make things too complicated. Weights could also be associated with edges in a similar manner (the number on the last edge a player traveled on is how many turns the other player gets). This is analogous to how in the real world certain areas are faster than others to get out of (a high number associated with the node effectively means it takes longer to leave that area).

We could also permit multigraphs with two-colored edges. That is, there can be multiple edges connecting the same pair of nodes, and the cop can only go on the blue colored edges, while the robber can only go on red colored edges. What this effectively does it make it so the players are playing with the same nodes, but different edges for each of them. This is analogous to people taking different routes when traveling.

The final generalization that came to mind is making it so when the cop touches a node (i.e. occupies it), the node is deleted for the rest of the pursuit. Of course, in order to make it so the robber doesn't trivially never have a winning strategy, we must be playing on an infinite graph. This could be analogous to a cop setting up a roadblock or a trap for the robber, thereby making it so the robber can never go to that node again.

I want to look into these generalizations and hopefully make some analyses on them once I have some time, but in the meantime, I thought I'd share these with y'all.

What do y'all think of these? Do y'all have any interesting generalizations that I didn't mention?
6 replies
Silverbach
Jan 6, 2017
cjquines0
Jan 13, 2017
J
H
Specific cop-robber graph families
cjquines0   17
N Jan 13, 2017 by ThE-dArK-lOrD
Here let’s try to compile named graph families and characterize them as cop- or robber-win.

Nowakowski already showed that all paths and trees are cop-win. Also, all cycles are robber-win.

Complete graphs are cop-win. For the general complete $r$-partite graph, as long as at least one of the $r$ sets has one vertex, then it’s cop-win: the cop just picks that vertex. Otherwise, if each of the $r$ sets has at least two vertices, it is robber-win: the strategy of the robber is to “follow-the-cop”, that is, whichever set the cop moves to, the robber moves to, but to a different vertex.

Polygon triangulations look like they are cop-win. My idea right now is to have a “cop-route” strategy for the cop: start him off at a vertex $v_1$ with degree 2, which always exists in a polygon triangulation. Then we have a path that goes through all vertices $v_1, v_2, \ldots$ for him to follow such that $v_i$ is adjacent to $v_{i-2}$, and it's okay to repeat vertices as long as the path is finite.

That way, the robber can’t be in $v_1$ in the first move. When the cop is in $v_2$, the robber can’t move to $v_1$ because he can catch him on the next turn. When the cop is in $v_3$, the robber can’t be at $v_1$ at all, since $v_1$ has only two neighbors $v_2$ and $v_3$. When the cop is in $v_4$, he is adjacent to both $v_2$ and $v_3$, so $v_4$ “covers” $v_1$. (In Nowakowski’s notation, $v_4 \geq_1 v_1$, I think.) The same logic goes for the rest of the vertices. (Alternatively, we can prove polygon triangulations are cop-win using Nowakowski’s theorems 1 or 2.)

Does anyone have other examples of graph families that are cop- or robber-win?
17 replies
cjquines0
Jan 7, 2017
ThE-dArK-lOrD
Jan 13, 2017
J
No more topics!
H
J
H
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
J