Felicia Halliday

An Overview of Spies and Revolutionaries

Spies and Revolutionaries is a vertex pursuit game played on graphs. There are two teams: $s$ spies and $r$ revolutionaries. Revolutionaries place their team first on vertices of the graph, then the spies are placed. Both teams have the option to move to an adjacent vertex or stay on the vertex they are on. If m revolutionaries are on the same vertex without a spy adjacent to them, then the revolutionaries win. If the spies can prevent this forever, spies win. Let $\sigma(G, m, r)$ denote the minimum number of spies needed to win. We will define some lower bounds, look at spy-win and spy-lose graphs, and show some open problems.