Realizable triples for stratified domination in graphs

Gera, Ralucca, and Zhang, Ping. "Realizable triples for stratified domination in graphs." Mathematica Bohemica 130.2 (2005): 185-202. <http://eudml.org/doc/249579>.

@article{Gera2005,
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 $(\{\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\}\}) \ne (k, k, \{\mathcal \{C\}\})$ for any integers $k$ and $\{\mathcal \{C\}\}$ with $\{\mathcal \{C\}\}> k \ge 2$.},
author = {Gera, Ralucca, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {stratified graph; $F$-domination; domination; open domination; stratified graph; -domination},
language = {eng},
number = {2},
pages = {185-202},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Realizable triples for stratified domination in graphs},
url = {http://eudml.org/doc/249579},
volume = {130},
year = {2005},
}

TY - JOUR
AU - Gera, Ralucca
AU - Zhang, Ping
TI - Realizable triples for stratified domination in graphs
JO - Mathematica Bohemica
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 130
IS - 2
SP - 185
EP - 202
AB - 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}}) \ne (k, k, {\mathcal {C}})$ for any integers $k$ and ${\mathcal {C}}$ with ${\mathcal {C}}> k \ge 2$.
LA - eng
KW - stratified graph; $F$-domination; domination; open domination; stratified graph; -domination
UR - http://eudml.org/doc/249579
ER -