Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
stratified graph; $F$-domination; domination; open domination
stratified graph; $F$-domination; domination; open domination
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$.
References:
[1] C. Berge: The Theory of Graphs and Its Applications. Methuen, London, 1962. MR 0132541 | Zbl 0097.38903
[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
[3] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratification and domination in graphs. Discrete Math. 272 (2003), 171–185. DOI 10.1016/S0012-365X(03)00078-5 | MR 2009541
[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 0483788
[6] R. Gera, P. Zhang: On stratification and domination in graphs. Preprint. MR 2330326
[7] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. MR 1605684
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, New York, 1998. MR 1605685
[9] O. Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Pub., Providence, RI, 1962. MR 0150753 | Zbl 0105.35401
[10] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph.D. Dissertation, Western Michigan University, 1994.
Search
Partner of
