Revolutionaries and spies: Spy-good and spy-bad graphs
We study a game on a graph G played by r revolutionaries and s spies. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a neighboring vertex or not move, and then each spy has the same option. The revolutionaries win if m of them meet at some vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let sigma T (G, m. r) denote the minimum number of spies needed to win. To avoid degenerate cases, assume [V(G)] >= r - m + 1 >= [r/m] >= 1. The easy bounds are then [r/m]   c' In n. For the hypercube Q(d) with d >= r, we have sigma (G, m, r) = r - m + 1 when m = 2, and for m >= 3 at least r - 39m spies are needed. For complete k-partite graphs with partite sets of size at least 2r, the leading term in sigma (G. m, r) is approximately k/k-1 r/m. when k >= m. For k = 2, we have sigma (G, 2, r) = [[7r/2]-3/5] and sigma (G, 3, r) = [r/2], and in general 3r/2m -3 <= sigma (G, m, r) <= (1+1/root 3)r/m. (C) 2012 Elsevier B.V. All rights reserved.
revolutionaries and spies hypercube graph searching graph game webbed tree random graph complete bipartite graph