Stratified Domination in Oriented Graphs

Abstract

An oriented graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let $H$ be a 2-stratified oriented graph rooted at some blue vertex. An $H$-coloring of an oriented graph $D$ is a red-blue coloring of the vertices of $D$ in which every blue vertex $v$ belongs to a copy of $H$ rooted at $v$ in $D$. The $H$-domination number ${\gamma }_H(D)$ is the minimum number of red vertices in an $H$-coloring of $D$. We investigate $H$-colorings in oriented graphs where $H$ is the red-red-blue directed path of order 3. Relationships between the $H$-domination number ${\gamma }_H$ and both the domination number $\gamma$ and open domination ${\gamma }_o$, in oriented graphs are studied. It is shown that $\gamma (D)\le {\gamma }_H(D)\le {\gamma }_o(D)\le \lfloor \frac{3{\gamma }_H(D)}{2}\rfloor$ for every oriented graph $D$. All pairs of positive integers that can be realized as (1) domination number and $H$-domination number and (2) the $H$-domination number and open domination number of some oriented graph are determined. Sharp bounds are established for the $H$-domination number of an $r$-regular oriented graph in terms of $r$ and its order.