No Access

INVERSE ROMAN DOMINATION IN GRAPHS

M. KAMAL KUMAR

VTU Belgaum, Karnataka, India

Search for more papers by this author

and

L. SUDERSHAN REDDY

Department of Mathematics, CMR Institute of Technology, Bangalore, India

Search for more papers by this author

https://doi.org/10.1142/S1793830913500110Cited by:4 (Source: Crossref)

Abstract

Motivated by the article in Scientific American [7], Michael A Henning and Stephen T Hedetniemi explored the strategy of defending the Roman Empire. Cockayne defined Roman dominating function (RDF) on a Graph G = (V, E) to be a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. For a real valued function f : V → R the weight of f is w(f) = ∑_v∈V f(v). The Roman domination number (RDN) denoted by γ_R(G) is the minimum weight among all RDF in G. If V – D contains a roman dominating function f¹ : V → {0, 1, 2}. "D" is the set of vertices v for which f(v) > 0. Then f¹ is called Inverse Roman Dominating function (IRDF) on a graph G w.r.t. f. The inverse roman domination number (IRDN) denoted by is the minimum weight among all IRDF in G. In this paper we find few results of IRDN.

Keywords:

AMSC: 05C69

References

Aris, Paolo, Konrad, Kathleen, David and Peter, Server placements, Roman Domination & Other Dominating Set Variants, IFIP-TCS 2002 . Google Scholar
B. Kinnersley et al. , SIAM J. Discr. Math. 23 , 1575 ( 2009 ) . Crossref, Google Scholar
K. S. Booth and J. H. Johnson , SIAM, J. Comput. 11 , 191 ( 1981 ) . Crossref, Google Scholar
E. J. Cockayne et al. , Util. Math. 67 , 19 ( 2005 ) . Google Scholar
C. S. ReVelle, Can you protect the Roman Empire? Johns Hopkins Magazine 49(2) (1997) 40 . Google Scholar
F. Harary , Graph Theory ( Addison Wiley , Reading Mass , 1975 ) . Google Scholar
I. Steward, Scientific American 281(6), 136 (1999). Crossref, Google Scholar
M. A. Henning, Discuss. Math. Graph Theory 22(2), 325 (2002). Crossref, Google Scholar
M. A. Henning and S. T. Hedetniemi , Disc Math. 266 , 239 ( 2003 ) . Crossref, Google Scholar
P. A. Dreyer, Defending the Roman Empire, Ph. D. Thesis, Rutgers University (2000) . Google Scholar
K. E. Rosign and C. S. ReVelle, Amer. Math. 107(7), 585 (2000). Crossref, Google Scholar
S. Hedetniemi , Roman domination the graphs II , Slides and Notes from 9th Quad. Int. Conf. Graph Theory, Combinatorics, Algorithms and Applications ( 2000 ) . Google Scholar
V. R. Kulli and S. C. Sigarkanti , Nat. Acad. Sci. Lett. 14 , 473 ( 1991 ) . Google Scholar
H. B. Walikar and R. L. Sudershan, Roman domination in special class of graphs, Ph. D. Thesis, Karnatak University, Dharwad (2008) . Google Scholar