Monopoly Free and Monopoly Cover in Graphs

Abstract

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)$ is the minimum cardinality of a monopoly set among all monopoly sets in $G$. In this paper, we introduce two type sets associated with a monopoly set, monopoly free and monopoly cover sets. A set $F\subseteq V$ is called a monopoly free of $G$ if $F$ does not contain any monopoly set as a subset. The monopoly free set is maximal if for every $v\notin F$ there exists $A\subseteq F$ such that $A \cup \{v\}$ is a monopoly. The cardinality of a largest maximal monopoly free set, denoted $mof(G)$, and is called a monopoly free size of $G$. A set $C \subseteq V$ is called a monopoly cover of $G$ if $C$ contains, at least, one vertex from each monopoly set in $G$. The cardinality of a minimum monopoly cover set in $G$, denoted by $moc(G)$, and is called a monopoly cover size of $G$. We investigate the relationship between these three parameters. Exact values of $mof(G)$ and $moc(G)$ for some standard graphs are found. Bounds for $mof(G)$ and $moc(G)$ are obtained. It is shown that $mof(G) + moc(G) =n$ for every graph $G$ of order $n$. Moreover, it is shown that for every integer $k\geq 3$ there exist a graph $G$ of order $n\geq6$ such that $mof(G)=moc(G)= mo(G)=k$. finally, we characterize all graphs $G$ with $mof(G)= 0, 1$ and $n-2$.