Revolutionaries and spies on trees and unicyclic graphs (Q1937355): Difference between revisions

The following game is played on a graph by two teams, a team of \(r\) revolutionaries and a team of \(s\) spies. Initially, the revolutionaries take position at the vertices of a graph, several revolutionaries may occupy the same vertex. Then the spies are placed at the vertices of the graph. In subsequent rounds, the revolutionaries may move to an adjacent vertex or stay where they are. Then the spies may move to an adjacent vertex. Spies and revolutionaries move alternately. The objective of the revolutionaries is to hold a meeting of at least \(m\) members without the presence of a spy. The spies win if they can prevent such an unguarded meeting of revolutionaries forever. The invention of this game is attributed to Jozef Beck, but no reference is given. It is shown, that if the game graph is a tree the trivial lower bound for the number of spies, namely \(\min\{|V(G)|, \lfloor r/m \rfloor \} \) is also sufficient for the spies to win. For unicyclic graphs, the necessary number of spies to win the game is obtained by changing the floor function in the spy number for trees to the ceiling function. Finally unicyclic graphs on which \(\lfloor r/m \rfloor +1\) spies are needed are characterized. The methods are elementary.