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

Abstract

Let $G=(V, E)$ be a simple graph without isolated vertices and minimum degree $\delta(G)$, and let $k\in \left\{1-\left\lceil \delta(G)/2\right\rceil,\ldots,\left\lfloor \delta(G)/2\right\rfloor\right\}$ 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)\ge \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.