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 σ(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⌋≤σ(G,m,r)≤r−m+1. We prove that the lower bound is sharp when G has a rooted spanning tree T such that every edge of G not in T joins two vertices having the same parent in T. As a consequence, σ(G,m,r)≤γ(G)⌊r/m⌋, where γ(G) is the domination number; this bound is nearly sharp when γ(G)≤m.For the random graph with constant edge-probability p, we obtain constants c and c′ (depending on m and p) such that σ(G,m,r) is near the trivial upper bound when rc′lnn. For the hypercube Qd with d≥r, we have σ(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 σ(G,m,r) is approximately when k≥m. For k=2, we have and σ(G,3,r)=⌊r/2⌋, and in general .