Revolutionaries and spies on random graphs

2012/05/02 by Dieter Mitsche, Mitsche, Dieter, Pawel Pralat +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1205.0531

arxiv created 2014/06/11 · arxiv updated 2014/06/12

Abstract

Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplified model for network security. In the game we consider in this paper, a team of r revolutionaries tries to hold an unguarded meeting consisting of m revolutionaries. A team of s spies wants to prevent this forever. For given r and m, the minimum number of spies required to win on a graph G is the spy number σ(G,r,m). We present asymptotic results for the game played on random graphs G(n,p) for a large range of p = p(n), r=r(n), and m=m(n). The behaviour of the spy number is analyzed completely for dense graphs (that is, graphs with average degree at least n^1/2+\eps for some \eps > 0). For sparser graphs, some bounds are provided.

Related

• Algorithms, hardness and graph products on a pursuit-evasion game
• Revolutionaries and Spies
• Cops and robbers in random graphs
• An anti-incursion algorithm for unknown probabilistic adversaries on connected graphs
• Containment game played on random graphs: another zig-zag theorem