Realizable triples for stratified domination in graphs
Ralucca Gera, Ping Zhang · Mathematica Bohemica · 2005
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 $({\mathcal A}, {\mathcal B}, {\mathcal C})$ of positive integers with ${\mathcal A}\le {\mathcal B}\le 2 {\mathcal A}$ and ${\mathcal B}\ge 2$ is realizable as the domination number, open domination number, and $F$-domination number, respectively, for some connected graph if and only if $({\mathcal A}, {\mathcal B}, {\mathcal C}) e (k, k, {\mathcal C})$ for any integers $k$ and ${\mathcal C}$ with ${\mathcal C}> k \ge 2$.