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
Cop-Win Graph Properties
iammosespaulr   9
N Dec 2, 2017 by JGeneson
For the cop to force a win situation the cop must be able to get the thief irrespective of the thief's choice to surrender.For cyclic graphs where there are no dominated vertices (one whose closed neighborhood is a subset of another vertex's neighborhood) i.e cyclic graphs which have the number of vertices $n>3$ and have their vertices connected only by the boundary of the cyclic structure , we find that the pilferer has a chance of completely evading the cop by just staying ahead of the cop this happens irrespective of the no of turns that he is given so the pilferer must win.We have already concluded that cyclic graphs which have vertex $n>3$ are pilferer win graphs so for the cop to win the graph must be a cyclic graph with $n\leq{3}$ or dismantle-able graph i.e it should be able to have a dominated vertex which can then be added or removed from the graph without affecting the end result to prove this let us assume the pilferer and the cop use their most effective strategies and they start in a cyclic graph with $n>{3}$ vertices, now adding a branch of length $p\leq{k/2}$ at point $L$ point such that there is an opportunity for the pilferer to get caught by entering the branch given that the branch terminates before he reaches $k/2$ turns, but since both the cop and the pilferer are using their effective strategies the pilferer will continue to evade the police by not entering the branch thereby producing the same result we had earlier i.e resulting in the pilferer evading the cop ,from this we could conclude that adding a branch which is essentially a chain of dominated vertices to a point on the graph does not change the outcome hence it must also be true for the converse leading the outcome to be unaffected even if you remove dominated vertices .Since we are allowed only $k/2$ turns the distance that the pilferer is allowed to travel must be $\leq{k/2}$ for a non-cyclic graph i.e terminating branched graphs.
I had written a simulation that would give the shortest route by mapping the various paths between the pilferer and the cop ,i may post it soon ..
9 replies
iammosespaulr
Nov 14, 2017
JGeneson
Dec 2, 2017
No more topics!
a