The Game of Revolutionaries and Spies on a Graph

We study a pursuit game between two teams on a graph; it can be viewed as modeling a problem of network security. The first team consists of $r$ revolutionaries; the second consists of $s$ spies. The revolutionaries seek a one-time meeting of $m$ revolutionaries free of oversight by spies. Initially, the revolutionaries take positions at vertices, and then the spies do the same. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. Everyone knows where everyone else is at all times.

The revolutionaries win if after a round there is an unguarded meeting, where a meeting consists of (at least) $m$ revolutionaries on one vertex, and it is unguarded if no spy is there. The spies win if they can prevent this forever.

We show that trees and unicyclic graphs are good for the spies in the following sense. For all fixed choices of $r$ and $m$, the minimum number of spies needed to win is $\lfloor \frac{r}{m} \rfloor$, which is clearly necessary, since the revolutionaries can form this many disjoint meetings. We call such graphs spy-good and describe a wider class of spy-good graphs. We also consider the game on hypercubes, large complete $k$-partite graphs, and graphs with small domination number.

This is joint work with Jane V. Butterfield, Gregory J. Puleo, Clifford D. Smyth, Douglas B. West, and Reza Zamani.

Speaker Bio: Daniel Cranston is an Assistant Math Professor at Virginia Commonwealth University, where he co-organizes the Discrete Math Seminar. His research is mainly in graph theory and algorithms, but he is also interested in most areas of discrete math. He received his PhD in computer science from the University of Illinois, where he was a student of Douglas West.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.