Ralucca Gera, Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu
Abstract: A 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 $F$ be a $2$-stratified graph rooted at some blue vertex $v$. An $F$-coloring of a graph $G$ is a red-blue coloring of the vertices of $G$ in which every blue vertex $v$ belongs to a copy of $F$ rooted at $v$. The $F$-domination number $\gamma_F(G)$ is the minimum number of red vertices in an $F$-coloring of $G$. In this paper, we study $F$-domination where $F$ is a red-blue-blue path of order 3 rooted at a blue end-vertex. It is shown that a triple $(\cA, \cB, \cC)$ of positive integers with $\cA\le\cB\le2 \cA$ and $\cB\ge2$ is realizable as the domination number, open domination number, and $F$-domination number, respectively, for some connected graph if and only if $(\cA, \cB, \cC) \ne(k, k, \cC)$ for any integers $k$ and $\cC$ with $\cC> k \ge2$.
Keywords: stratified graph, $F$-domination, domination, open domination
Classification (MSC2000): 05C15, 05C69
Full text of the article: