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: