Realizable triples for stratified domination in graphs

Gera, Ralucca ; Zhang, Ping

Mathematica Bohemica, Tome 130 (2005) no. 2, pp. 185-202.

Résumé

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$.

Détail

DOI : 10.21136/MB.2005.134128

Classification : 05C15, 05C69
Keywords: stratified graph; $F$-domination; domination; open domination