The Monopoly in the Join of Graphs

Ahmed M. Naji, Nandappa D. Soner


In a graph \(G = (V,E)\), a set \(M\subseteq V(G)\) is said to be a monopoly set of \(G\) if every vertex \(v\in V-M\) has, at least, \(\frac{d(v)}{2}\) neighbors in \(M\). The monopoly size \(mo(G)\) of \(G\) is the minimum cardinality of a monopoly set among all monopoly sets of \(G\). A join graph is the complete union of two arbitrary graphs. In this paper, we investigate the monopoly set in the join of graphs. As consequences the monopoly size of the join of graphs is obtained. Upper and lower bound of the monopoly size of join graphs are obtained. The exact values of monopoly size for the join of some standard graphs with others are obtained.


Monopoly set; Monopoly size; Join of graphs; Monopoly size of join of graphs

Full Text:



E. Berger, Dynamic monopolies of constant size, J. Combi. Theory, Series B 83 (2001), 191 – 200.

J. Bermond, J. Bond, D. Peleg and S. Perennes, The power of small coalitions in graphs, Disc. Appl. Math. 127 (2003), 399 – 414.

B. Bolloba’s, Modern Graph Theory, Springer Sci. Busin. Media, New York (1998).

P. Flocchini, R. Kralovic, A. Roncato, P. Ruzicka and N. Santoro, On time versus size for monotone dynamic monopolies in regular topologies, J. Disc. Algor. 1 (2003), 129 – 150.

F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.- London (1969).

K. Khoshkhak, M. Nemati, H. Soltani and M. Zaker, A study of monopoly in graphs, Graph and Combi. Math. 29 (2013), 1417 – 1427.

A. Mishra and S.B. Rao, Minimum monopoly in regular and tree graphs, Discrete Mathematics 306(14) (2006), 1586 – 1594.

A.M. Naji and N.D. Soner, Independent monopoly size in graphs, Appl. Appl. Math. Intern. J. 10(2) (2015), 738 – 749.

A.M. Naji and N.D. Soner, Monopoly free and monopoly cover sets in graphs, Int. J. Math. Appl. 4(2-A)(2016), 71 – 77.

A.M. Naji and N.D. Soner, On the Monatic number of a graph, Int. J. Adv. Appl. Math. Mech. 4(2) (2016), 44 – 51.

A.M. Naji and N.D. Soner, On the monopoly of graphs, Proc. Jang. Math. Soc. 2(18) (2015), 201 – 210.

A.M. Naji and N.D. Soner, Partitioning a graph into monopoly sets, TWMS J. Appl. Engin. Math., 7(1) (2017), 154 – 164.

A.M. Naji and N.D. Soner, The connected monopoly in graphs, Intern. J. Multi. Resear. Devle. 2(4) (2015), 273 – 277.

A.M. Naji and N.D. Soner, The maximal monopoly of graphs, J. Comp. Math. Sci. 6(1) (2015), 33 – 41.

D. Peleg, Local majorities; coalitions and monopolies in graphs; a review, Theor. Comp. Sci. 282 (2002), 231 – 257.

M. Zaker, On dynamic monopolies of graphs with general thresholds, Disc. Math. 312 (2012), 1136 – 1143.


eISSN 0975-5748; pISSN 0974-875X