A Study of Monopolies in Graphs

In a graph G, a set D of vertices is said to be a monopoly if any vertex ${v\in V(G) \setminus D}$ has at least deg(v)/2 neighbors in D. A strict monopoly is defined similarly when we replace deg(v)/2 by deg(v)/2 + 1 for any vertex v whose degree is even number. By the monopoly size (resp. strict monopoly size) of G we mean the smallest cardinality of a monopoly (resp. strict monopoly) in G. We first discuss the basic bounds for the monopoly and strict monopoly size of graphs. In the second section we show relationships between matchings and monopolies and present some upper bounds for the monopoly and strict monopoly size of graphs in terms of the matching number of graphs. The third section is devoted to presenting some lower bounds for the monopoly size of graphs in terms of the even-girth and odd-girth of graphs.