PARTITIONING A GRAPH INTO MONOPOLY SETS

Abstract

In a graph G = (V, E), a set M ? V (G) is said to be a monopoly set ofG if every vertex v ? V - M has, at least,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 agraph G is the partition of V (G) into k disjoint monopoly sets. The monatic number ofG, denoted by µ(G), is the maximum number of sets in M-partition of G. It is shownthat 2 <= µ(G) <= 3 for every graph G without isolated vertices. The properties of eachmonopoly 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 Eulerianand have ?(G) <= 3. Finally, it is shown that for every integer k /? {1, 2, 4}, there existsa graph G of order n = k having µ(G) = 3.