| Title:
|
Realizable triples for stratified domination in graphs (English) |
| Author:
|
Gera, Ralucca |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
130 |
| Issue:
|
2 |
| Year:
|
2005 |
| Pages:
|
185-202 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
stratified graph |
| Keyword:
|
$F$-domination |
| Keyword:
|
domination |
| Keyword:
|
open domination |
| MSC:
|
05C15 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1112.05076 |
| idMR:
|
MR2148652 |
| DOI:
|
10.21136/MB.2005.134128 |
| . |
| Date available:
|
2009-09-24T22:20:05Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134128 |
| . |
| Reference:
|
[1] C. Berge: The Theory of Graphs and Its Applications.Methuen, London, 1962. Zbl 0097.38903, MR 0132541 |
| Reference:
|
[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 1772755 |
| Reference:
|
[3] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratification and domination in graphs.Discrete Math. 272 (2003), 171–185. MR 2009541, 10.1016/S0012-365X(03)00078-5 |
| Reference:
|
[4] G. Chartrand, P. Zhang: Introduction to Graph Theory.McGraw-Hill, Boston, 2005. |
| Reference:
|
[5] E. J. Cockayne, S. T. Hedetniemi: Towards a theory of domination in graphs.Networks (1977), 247–261. MR 0483788 |
| Reference:
|
[6] R. Gera, P. Zhang: On stratification and domination in graphs.Preprint. MR 2330326 |
| Reference:
|
[7] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998. MR 1605684 |
| Reference:
|
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics.Marcel Dekker, New York, 1998. MR 1605685 |
| Reference:
|
[9] O. Ore: Theory of Graphs.Amer. Math. Soc. Colloq. Pub., Providence, RI, 1962. Zbl 0105.35401, MR 0150753 |
| Reference:
|
[10] R. Rashidi: The Theory and Applications of Stratified Graphs.Ph.D. Dissertation, Western Michigan University, 1994. |
| . |
