Roman and inverse Roman domination in graphs

Zulfiqar Zaman, M. Kamal Kumar and Saad Salman Ahmad
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 24, 2018, Number 3, Pages 142–150
DOI: 10.7546/nntdm.2018.24.3.142-150
Full paper (PDF, 162 Kb)

Details

Authors and affiliations

Zulfiqar Zaman
Department of Mathematics, Higher College of Technology
Muscat, Oman

M. Kamal Kumar
Department of Mathematics, Higher College of Technology
Muscat, Oman

Saad Salman Ahmad
Department of Mathematics, Higher College of Technology
Muscat, Oman

Abstract

Motivated by the article in Scientific American [8], 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  is  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}, where 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 γ¹_R(G) is the minimum weight among all IRDF in G. In this paper we find few results of RDN and IRDN.

Keywords

• Domination number
• Inverse domination number
• Roman domination number

2010 Mathematics Subject Classification

• 05C69

References

1. Berge, C. (1958) Theory of Graphs and Its Applications, Methuen, London.
2. Harary, F. (1975) Graph Theory, Addison Wiley, Reading Mass.
3. Henning, M. A., & Hedetniemi, S. T. (2003) Defending the Roman Empire – A new strategy, Discrete Mathematics, 266, 239–251.
4. Kamal Kumar, M., & Murali, R. (2014) Inverse Roman domination in some classes of graphs. International Journal of Computer Application, 4(4), 219–238.
5. Kamal Kumar, M., & Sudershan Reddy, L. (2013) Inverse Roman domination in graphs, Discrete Mathematics Algorithm and Application, 5(3), 1–4.
6. Ore, O. (1962) Theory of Graphs. American Mathematical Society Colloquium Publications, 38 (American Mathematical Society, Providence, RI).
7. ReVelle. C. S, Rosing. K. E. (2000) Defendens imperium Romanum: A classical problem in military, Strategy, Amer. Math. Monthly, 107(7), 585–594.
8. Stewart, I. (1999) Defend the Roman Empire! Scientific American, 281(6), 136–139.