# On stratification and domination in graphs

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 2, page 249-272
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRalucca Gera, and Ping Zhang. "On stratification and domination in graphs." Discussiones Mathematicae Graph Theory 26.2 (2006): 249-272. <http://eudml.org/doc/270514>.

@article{RaluccaGera2006,

abstract = {A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), 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 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 $γ_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 2-stratified red-blue-blue path of order 3 rooted at a blue end-vertex. We present characterizations of connected graphs of order n with F-domination number n or 1 and establish several realization results on F-domination number and other domination parameters.},

author = {Ralucca Gera, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {stratified graph; F-domination; domination; -domination},

language = {eng},

number = {2},

pages = {249-272},

title = {On stratification and domination in graphs},

url = {http://eudml.org/doc/270514},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Ralucca Gera

AU - Ping Zhang

TI - On stratification and domination in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 2

SP - 249

EP - 272

AB - A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), 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 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 $γ_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 2-stratified red-blue-blue path of order 3 rooted at a blue end-vertex. We present characterizations of connected graphs of order n with F-domination number n or 1 and establish several realization results on F-domination number and other domination parameters.

LA - eng

KW - stratified graph; F-domination; domination; -domination

UR - http://eudml.org/doc/270514

ER -

## References

top- [1] B. Bollobas and E.J. Cockayne, The irredundance number and maximum degree of a graph, Discrete. Math. 49 (1984) 197-199, doi: 10.1016/0012-365X(84)90118-3. Zbl0539.05056
- [2] G. Chartrand, H. Gavlas, M.A. Henning and R. Rashidi, Stratidistance in stratified graphs, Math. Bohem. 122 (1997) 337-347. Zbl0898.05023
- [3] G. Chartrand, T.W. Haynes, M.A. Henning and P. Zhang, Stratification and domination in graphs, Discrete Math. 272 (2003) 171-185, doi: 10.1016/S0012-365X(03)00078-5. Zbl1028.05074
- [4] G. Chartrand, T.W. Haynes, M.A. Henning and P. Zhang, Stratified claw domination in prisms, J. Combin. Math. Combin. Comput. 33 (2000) 81-96. Zbl0954.05036
- [5] G. Chartrand, L. Holley, R. Rashidi and N.A. Sherwani, Distance in stratified graphs, Czech. Math. J. 125 (2000) 135-146. Zbl1033.05031
- [6] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Boston, 2005). Zbl1096.05001
- [7] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. Zbl0447.05039
- [8] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Markus, Restrained domination, preprint.
- [9] J.F. Fink and M.S. Jacobson, n-Domination in graphs, in: Y. Alavi and A.J. Schwenk, eds, Graph Theory with Applications to Algorithms and Computer Science, 283-300 (Kalamazoo, MI 1984), Wiley, New York, 1985.
- [10] R. Rashidi, The Theory and Applications of Stratified Graphs (Ph.D. Dissertation, Western Michigan University, 1994).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.