Dan Cranston
Spies and Revolutionaries (on Graphs)

Abstract: We study a game played on a graph G by a team of r revolutionaries and a team of s spies. Initially, revolutionaries and then spies take positions at vertices. In each subsequent round, each revolutionary can move to an adjacent vertex or stay put, and then each spy has the same options. The revolutionaries try to get a meeting, meaning m revolutionaries at some vertex with no spy present (at the end of a round).

For each graph G and meeting size m, there is a threshold for s in terms of r and m that lets the spies keep the revolutionaries from winning; revolutionaries always win if s < floor(r/m), where "floor(x)" means the greatest integer no larger than x. For any graph G having at most one cycle, we determine who wins for all m, r, s. In most cases, the spies win if and only if s >= floor(r/m), but sometimes one more spy is needed.