Computing the ($k$-)monopoly Number of Direct Product of Graphs

Dorota Kuziak, Iztok Peterin, Ismael G. Yero

Let $G=(V,E)$ be a simple graph without isolated vertices and minimum degree $\delta(G)$, and let $k\in\{1-\lceil\delta(G)/2\rceil,\ldots,\lfloor\delta(G)/2\rfloor\}$ be an integer. Given a set $M\subset V$, a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_M(v)\geq\frac{\delta(v)}2+k$ where $\delta_M(v)$ represents the quantity of neighbors $v$ has in $M$ and $\delta(v)$ the degree of $v$. The set $M$ is called a $k$-monopoly if it $k$-controls every vertex $v$ of $G$. The minimum cardinality of any $k$-monopoly is the $k$-monopoly number of $G$. In this article we study the $k$-monopoly number of direct product graphs. Specifically we obtain tight lower and upper bounds for the $k$-monopoly number of direct product graphs in terms of the $k$-monopoly numbers of its factors. Moreover, we compute the exact value for the $k$-monopoly number of several families of direct product graphs.