Some Results on the Strong Roman Domination Number of Graphs

Document Type : Original Scientific Paper


1 Department of Mathematics, Payame Noor University, I. R. Iran

2 Department of Mathematics, Dehloran Branch, University of Applied Science and Technology Dehloran, I. R. Iran

3 Faculty of Mathematical Sciences, University of Tabriz, Tabriz, I. R. Iran


Let G=(V,E) be a finite and simple graph of order n and maximum‎ ‎degree Δ(G)‎. ‎A strong Roman dominating function on a‎ ‎graph  G  is a function  f‎:V (G)→{0‎, ‎1,… ,‎\lceil‎ ‎ Δ(G)/2 \rceil‎+ ‎1}  satisfying the condition that every‎ ‎vertex v for which  f(v)=0  is adjacent to at least one vertex  u ‎for which‎ f(u) ≤ 1‎+ ‎\lceil \frac{1}{2}| N(u) ∩ V0| \rceil‎, ‎where V0={v ∊ V | f(v)=0}. The minimum of the‎ values \sumv∊ V f(v), ‎taken over all strong Roman dominating‎ ‎functions f of G‎, ‎is called the strong Roman domination‎ ‎number  of G and is denoted by γStR(G)‎. ‎In this paper we‎ ‎continue the study of strong Roman domination number in graphs‎. ‎In‎ particular‎, ‎we present some sharp bounds for γStR(G) and‎ we determine the strong Roman domination number of some graphs‎.


[1] M. P. Álvarez-Ruiz, I. González Yero, T. Mediavilla-Gradolph, S. M. Sheikholeslami and J. C. Valenzuela-Tripodoro, On the Strong Roman Domination Number of Graphs, Discrete Applied Math. 231 (2017) 44 - 59.
[2] J. A. Bondy and U. S. R. Murty,
Graph Theory with Applications, American Elsevier, New York, 1976.
[3] E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for Roman domination, J. Discrete Math.
23 (2009) 1575 - 1586.
[4] C. S. Revelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy,
Amer. Math. Monthly 107 (7) (2000) 585-594.
[5] I. Stewart, Defend the Roman Empire,
Sci. Amer. 281 (6) (1999) 136 - 139.