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) \leq \gamma_H(D) \leq \gamma_o(D) \leq \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.