Geodesic
Realizable triples for stratified domination in graphs
Mathematica Bohemica, Tome 130 (2005) no. 2, pp. 185-202
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/MB.2005.134128
Classification : 05C15, 05C69
Keywords: stratified graph; $F$-domination; domination; open domination 
@article{10_21136_MB_2005_134128,
     author = {Gera, Ralucca and Zhang, Ping},
     title = {Realizable triples for stratified domination in graphs},
     journal = {Mathematica Bohemica},
     pages = {185--202},
     year = {2005},
     volume = {130},
     number = {2},
     doi = {10.21136/MB.2005.134128},
     mrnumber = {2148652},
     zbl = {1112.05076},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134128/}
}
TY  - JOUR
AU  - Gera, Ralucca
AU  - Zhang, Ping
TI  - Realizable triples for stratified domination in graphs
JO  - Mathematica Bohemica
PY  - 2005
SP  - 185
EP  - 202
VL  - 130
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134128/
DO  - 10.21136/MB.2005.134128
LA  - en
ID  - 10_21136_MB_2005_134128
ER  - 
%0 Journal Article
%A Gera, Ralucca
%A Zhang, Ping
%T Realizable triples for stratified domination in graphs
%J Mathematica Bohemica
%D 2005
%P 185-202
%V 130
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134128/
%R 10.21136/MB.2005.134128
%G en
%F 10_21136_MB_2005_134128
Gera, Ralucca; Zhang, Ping. Realizable triples for stratified domination in graphs. Mathematica Bohemica, Tome 130 (2005) no. 2, pp. 185-202. doi: 10.21136/MB.2005.134128

[1] C. Berge: The Theory of Graphs and Its Applications. Methuen, London, 1962. | MR | Zbl

[2] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratified claw domination in prisms. J. Comb. Math. Comb. Comput. 33 (2000), 81–96. | MR

[3] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratification and domination in graphs. Discrete Math. 272 (2003), 171–185. | DOI | MR

[4] G. Chartrand, P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.

[5] E. J. Cockayne, S. T. Hedetniemi: Towards a theory of domination in graphs. Networks (1977), 247–261. | MR

[6] R. Gera, P. Zhang: On stratification and domination in graphs. Preprint. | MR

[7] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. | MR

[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, New York, 1998. | MR

[9] O. Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Pub., Providence, RI, 1962. | MR | Zbl

[10] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph.D. Dissertation, Western Michigan University, 1994.

Cité par Sources :