Graph Immunity Against Local Influence
David Peleg · 1996
This paper considers the question of the influence of a coalition of vertices, seeking to gain control (or majority) in local neighborhoods in a general graph. A vertex v is said to be controlled by the coalition M if the majority of its neighbors are from M. Let Ruled(G,M) denote the set of vertices controlled by M in G. Previous studies focused on constructions allowing small coalitions to control many vertices, and provided tight bounds for the maximum possible |Ruled(G,M)| (as a function of |M|). This paper introduces the dual problem, concerning the existence of graphs immune to the influence of small coalitions, i.e., graphs G for which Ruled(G,M) is small (relative to |M| again) for every coalition M. Upper and lower bounds are derived on the extent to which such immunity can be achieved.