Originators: József Beck (presented by Gregory Puleo - REGS 2011; also in REGS 2010 by David Howard)
Definitions: Let G be a graph and let m, r, s be positive integers. The game RS(G,m,r,s) is played on G by a team of r revolutionaries and a team of s spies. Initially, each revolutionary occupies a vertex, and then each spy occupies a vertex (vertices may have any number of revolutionaries and any number of spies). In each subsequent round, each revolutionary has the option to move to a neighboring vertex or not move. After the revolutionaries, each spy also has this option.
The revolutionaries win if, at the end of a round (or after the initial placements), there is a vertex hosting an unguarded meeting of m revolutionaries with no spy. The spies win if they have a strategy to prevent this forever. Since having extra players cannot hurt the spies, we define σ(G,m,r) to be the minimum number of spies needed to win against r revolutionaries playing on G with meeting size m.
Background: Always σ(G,m,r) ≥ min(|V(G)|, ⌊r/m⌋), since the revolutionaries can make ⌊r/m⌋ meetings initially if enough vertices are available. A graph is spy-good if this many spies always suffice. On the other hand, σ(G,m,r) ≤ r-m+1, since when the spies follow this many distinct revolutionaries, the remaining m-1 revolutionaries cannot form an unguarded meeting. A graph is spy-bad if this many spies are needed.
In the mid 1990s, Cliff Smyth showed that trees are spy-good. This is extended in [CSW] to show that ⌈r/m⌉ spies suffice when G has exactly one cycle, in fact determining also when ⌈r/m⌉ spies suffice. In [HS], the game is studied on the integer lattice with horizontal, vertical, and diagonal edges; with meeting size 2, about (3/4)r spies are needed to win.
This game was studied extensively in REGS 2010 and subsequent work (see [BCPWZ]), where it was shown that interval graphs and graphs with dominating vertices are spy-good, while hypercubes are spy-bad. Also complete multipartite graphs are "spy-goodish", since there the number of spies needed is approximately a small constant multiple of r/m. In contrast to interval graphs, for each r and m there is a chordal graph (and a bipartite graph) such that r-m+1 spies are needed to win. Many interesting questions remain.
Problem 1: Determine σ for the Petersen graph and its generalizations, such as Kneser graphs and cycle permutation graphs.
Question 2: It is relatively easy to show that σ(G,m,r,) ≤ γ(G)⌊r/m⌋, where γ(G) is the domination number of G. For which graphs does equality hold, especially among graphs with domination number 2? Alternatively, can the upper bound be improved?
Question 3: If G is finite and the revolutionaries can win RS(G,m,r,s), they can win within N moves, where N is something like the total number of configurations of r revolutionaries and s spies on G. Is there a better bound on N in terms of the parameters of G? In particular, is there a bound in terms of the diameter?
Question 4: What structural properties of a graph ensure that it is spy-good or spy-bad? (or within a constant factor of either?)
Question 5: Both the complete graph and its complement are spy-good. What are the extremal non-spy-good graphs on n vertices? That is, what are the least and greatest numbers of edges in n-vertex graphs that are not spy-good?
Question 6: What is the complexity of recognizing who wins RS(G,m,r,s)?
References:
[CSW] D.W. Cranston, C. Smyth, and D.B. West, Revolutionaries and spies in
trees and unicyclic graphs.
[HS] D. Howard and C. Smyth, Revolutionaries and spies in grid-like graphs
(submitted).
[BCPWZ] J. Butterfield, D.W. Cranston, G.J. Puleo, D.B. West, and R. Zamani,
Revolutionaries and spies: Spy-good and spy-bad graphs.