ArticleOriginal scientific text

Title

Weak roman domination in graphs

Authors 1, 2

Affiliations

  1. D.B. Jain College, Chennai - 600 097, Tamil Nadu, India
  2. SRR Engineering College, Chennai - 603 103, Tamil Nadu, India

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)=vVf(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.

Keywords

domination number, weak Roman domination number

Bibliography

  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.
  2. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, (Eds), Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  3. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, (Eds), Domination in Graphs; Advanced Topics (Marcel Dekker, Inc. New York, 1998).
  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.
  5. M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 325-334, doi: 10.7151/dmgt.1178.
  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.
  7. C.S. ReVelle, Can you protect the Roman Empire?, John Hopkins Magazine (2) (1997) 70.
  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.
  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.
  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.
  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.
  12. I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139.
Pages:
161-170
Main language of publication
English
Received
2009-11-07
Accepted
2010-04-02
Published
2011
Exact and natural sciences