PARTITIONING A GRAPH INTO MONOPOLY SETS

Abstract

In a graph G = V, E , a subset M of V G is said to be a monopoly set of G if every vertex v ∈ V - M has, at least, d v / 2 neighbors in M. The monopoly size of G, denoted by mo G , is the minimum cardinality of a monopoly set. In this paper, we study the problem of partitioning V G into monopoly sets. An M-partition of a graph G is the partition of V G into k disjoint monopoly sets. The monatic number of G, denoted by μ G , is the maximum number of sets in M-partition of G. It is shown that 2 ≤ μ G ≤ 3 for every graph G without isolated vertices. The properties of each monopoly partite set of G are presented. Moreover, the properties of all graphs G having μ G = 3, are presented. It is shown that every graph G having μ G = 3 is Eulerian and have χ G ≤ 3. Finally, it is shown that for every integer k which is different from {1, 2, 4}, there exists a graph G of order n = k having μ G = 3.

Keywords

• vertex degrees,distance in graphs,graph polynomials.

References

1. Aharoni,R., Milner,E.C., and Prikry,K., Unfriendly partitions of a graph, J. Combin. Theory, Series B, 50(1)( 1990), pp.1-10.
2. Berger,E., Dynamic monopolies of constant size, J. Combin. Theory, Series B, 83(2001),pp.191-200.
3. Bermond,J., Bond,J., Peleg,D., and Perennes,S., The power of small coalitions in graphs, Disc. Appl. Math., 127(2003), pp.399-414.
4. Bondy,J.A. and Murty,U.S.R., Graph Theory, Springer, Berlin, 2008.
5. Borodin,A.V. and Kostochka,A.V., A note on an upper bound of a graph’s chromatic number, depend- ing on the graph’s degree and density, J. Combin. Theory Series B, 23(1977), pp.247-250.
6. Cockayne,E.J. and Hedetniemi,S.T., Towards a theory of domination in graphs, Networks, 7(1977), pp.247-261.
7. Flocchini,P., Kralovic,R., Roncato,A., Ruzicka,P., and Santoro,N., On time versus size for monotone dynamic monopolies in regular topologies, J. Disc. Algor., 1(2003), pp.129-150.
8. Harary,F., Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, Haynes,T.W., Hedetniemi,S.T., and Slater,P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.

9. Khoshkhak,K., Nemati,M., Soltani,H., and Zaker,M., A study of monopoly in graphs, Graph and Combi. Math., 29(2013), pp.1417-1427.
10. Mishra,A. and Rao,S.B., Minimum monopoly in regular and tree graphs, Disc. Math., 306(14) (2006), pp.1586-1594.
11. Naji,A.M. and Soner,N.D., On the monopoly of graphs, Proce. Jang. Math. Soci., 2(18)(2015), pp.201
12. Naji,A.M. and Soner,N.D., The maximal monopoly of graphs, J. Comp. Math. Scien., 6(1)(2015), pp.33-41.
13. Naji,A.M. and Soner,N.D., The connected monopoly in graphs, intern. J. Multi. Resear. Devle., (4)(2015), pp.273-277.
14. Naji,A.M. and Soner,N.D., Independent monopoly size in graphs, Appl. Appl. Math. Intern. J., 10(2) (2015), pp.738-749.
15. Naji,A.M. and Soner,N.D., Monopoly Free and Monopoly Cover Sets in Graphs, Int. J. Math. Appl., (2A)(2016), pp.71-77.
16. Peleg,D., Local majorities; coalitions and monopolies in graphs; a review, Theor. Comp. Sci., (2002), pp.231-257.
17. Sigarreta,J.M., Yero,I.G., Bermudo,S., and Rodrguez-Velzquez,J.A., Partitioning a graph into offen- sive k-alliances, Disc. Appl. Math. 159(2011), pp.224-231.
18. Zaker,M., On dynamic monopolies of graphs with general thresholds, Disc. Math., 312(2012), pp.1136- https://en.wikipedia.org/wiki/Pigeonhole-principle.
19. Ahmed Mohammed Naji was born in Yemen. He got his B.Sc. degree in math- ematics and