Loading...
Please wait, while we are loading the content...
Similar Documents
Tight bounds on the size of 2-monopolies (1996).
| Content Provider | CiteSeerX |
|---|---|
| Author | Bermond, J.-C. Bond, J. Peleg, D. Perennes, S. |
| Abstract | This paper 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, establishing that in an n-vertex graph, an r-monopoly M (for any even r 2) must be of size \Omega\Gamma n 3=5 ), and that for any r 2 there exist n-vertex graphs with r-monopolies of size O(n 3=5 ). This settles a problem left open in [LPRS93, BePe95]. |
| File Format | |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Tight Bound Exist N-vertex Graph N-vertex Graph Size Omega Gamma Local Neighborhood |
| Content Type | Text |
| Resource Type | Article |
