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 (MSC 2000): 05C15, 05C69
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.