Weak roman domination in graphs

P. Roushini Leely Pushpam; T.N.M. Malini Mai

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 161-170
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph and f be a function f:V → 0,1,2. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f’: V → 0,1,2 defined by f’(u) = 1, f’(v) = f(v)-1 and f’(w) = f(w) if w ∈ V-u,v, has no undefended vertex. The weight of f is w ( f ) = ∑ v ∈ V f ( v ) . The weak Roman domination number, denoted by γ r ( G ) , is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which γ r ( G ) = γ ( G ) and find γ r -value for a caterpillar, a 2×n grid graph and a complete binary tree.

How to cite

top

P. Roushini Leely Pushpam, and T.N.M. Malini Mai. "Weak roman domination in graphs." Discussiones Mathematicae Graph Theory 31.1 (2011): 161-170. <http://eudml.org/doc/270829>.

@article{P2011,
abstract = {Let G = (V,E) be a graph and f be a function f:V → 0,1,2. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f’: V → 0,1,2 defined by f’(u) = 1, f’(v) = f(v)-1 and f’(w) = f(w) if w ∈ V-u,v, has no undefended vertex. The weight of f is $w(f) = ∑_\{v ∈ V\}f(v)$. The weak Roman domination number, denoted by $γ_r(G)$, is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which $γ_r(G) = γ(G)$ and find $γ_r$-value for a caterpillar, a 2×n grid graph and a complete binary tree.},
author = {P. Roushini Leely Pushpam, T.N.M. Malini Mai},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; weak Roman domination number},
language = {eng},
number = {1},
pages = {161-170},
title = {Weak roman domination in graphs},
url = {http://eudml.org/doc/270829},
volume = {31},
year = {2011},
}

TY - JOUR
AU - P. Roushini Leely Pushpam
AU - T.N.M. Malini Mai
TI - Weak roman domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 161
EP - 170
AB - Let G = (V,E) be a graph and f be a function f:V → 0,1,2. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f’: V → 0,1,2 defined by f’(u) = 1, f’(v) = f(v)-1 and f’(w) = f(w) if w ∈ V-u,v, has no undefended vertex. The weight of f is $w(f) = ∑_{v ∈ V}f(v)$. The weak Roman domination number, denoted by $γ_r(G)$, is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which $γ_r(G) = γ(G)$ and find $γ_r$-value for a caterpillar, a 2×n grid graph and a complete binary tree.
LA - eng
KW - domination number; weak Roman domination number
UR - http://eudml.org/doc/270829
ER -

References

top
  1. [1] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 78 (2004) 11-22, doi: 10.1016/j.disc.2003.06.004. Zbl1036.05034
  2. [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, (Eds), Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, (Eds), Domination in Graphs; Advanced Topics (Marcel Dekker, Inc. New York, 1998). Zbl0883.00011
  4. [4] S.T. Hedetniemi and M.A. Henning, Defending the Roman Empire - A new strategy, Discrete Math. 266 (2003) 239-251, doi: 10.1016/S0012-365X(02)00811-7. Zbl1024.05068
  5. [5] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 325-334, doi: 10.7151/dmgt.1178. Zbl1030.05093
  6. [6] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115, doi: 10.1016/S0012-365X(03)00040-2. Zbl1022.05055
  7. [7] C.S. ReVelle, Can you protect the Roman Empire?, John Hopkins Magazine (2) (1997) 70. 
  8. [8] C.S. ReVelle and K.E. Rosing, Defendens Romanum: Imperium problem in military strategy, American Mathematical Monthly 107 (2000) 585-594, doi: 10.2307/2589113. Zbl1039.90038
  9. [9] R.R. Rubalcaba and P.J. Slater, Roman Dominating Influence Parameters, Discrete Math. 307 (2007) 3194-3200, doi: 10.1016/j.disc.2007.03.020. Zbl1127.05075
  10. [10] P. Roushini Leely Pushpam and T.N.M. Malini Mai, On Efficient Roman dominatable graphs, J. Combin Math. Combin. Comput. 67 (2008) 49-58. Zbl1189.05138
  11. [11] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Edge Roman domination in graphs, J. Combin Math. Combin. Comput. 69 (2009) 175-182. Zbl1195.05056
  12. [12] I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139. 

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.