Tight bounds on the size of 2-monopolies

Description

This papers deals with the question of the influence of a monopoly of vertices, seeking to gain the majority in local neighborhoods in a graph. Say that a vertex v is r-controlled by a set of vertices M if the majority of its neighbors at distance r are from M. We ask how large must M be in order to r-monopolize the graph, namely, r-control every vertex. Tight upper and lower bounds are provided for this problem. For any even ≥ 2, an r-monopoly M in an n-vertex graph must be of size Ω(n"/5), and there exist n-vertex graphs with r-monopolies of size O(n3/5).

Abstract

International audience

Additional details