ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

The Game of Revolutionaries and Spies on a Graph

Daniel Cranston
Department of Mathematics, Virginia Commonwealth University

Tuesday, March 12, 2013 15:00-16:00,
Building 101, Lecture Room D
Tuesday, March 12, 2013 13:00-14:00,
Room 1-4058


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

Contact: B. Cloteaux

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

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2013-03-12.