A study of k−monopoly of graphs

For years, there has been a vast variety of applications for monopolies since graph theorists rst modeled by means of graphs the real-life problems for which concepts like controlling and eect are needed. Soon after then, a quite long range of approaches around the notion of domination has been applied to dierent problems including the spread of diseases or viruses in social and viral networks, respectively, and so on. A set M in a graph G = (V;E) is called a k-monopoly if it k-controls every vertex v of G, that is, M(v)  (v)=2 + k where M(v) represents the number of neighbors v has in M. The minimum cardinality of a k-monopoly of G is the k-monopoly number of G. Here, we study the k-monopoly number of graphs and initiate our work by determining a lower bound for k-monopolies of Cartesian graphs in terms of their maximum and minimum degrees. We also investigate the parameter to obtain in the last section an upper bound for the monopoly number of a graph by use of the probabilistic techniques. Finally, to oer additional insights into the concept from probabilistic point of view, we present a sketch of changes in the monopoly number on a 3-dimentional diagram in terms of the minimum degree of graphs.

Keywords: k-monopoly, Cartesian product, upper bound, lower bound.