On stratification and domination in graphs

Ralucca Gera; Ping Zhang

Discussiones Mathematicae Graph Theory (2006)

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

Abstract

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

How to cite

top

Ralucca 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. [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. [2] G. Chartrand, H. Gavlas, M.A. Henning and R. Rashidi, Stratidistance in stratified graphs, Math. Bohem. 122 (1997) 337-347. Zbl0898.05023
  3. [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. [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. [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. [6] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Boston, 2005). Zbl1096.05001
  7. [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. [8] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Markus, Restrained domination, preprint. 
  9. [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. [10] R. Rashidi, The Theory and Applications of Stratified Graphs (Ph.D. Dissertation, Western Michigan University, 1994). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.