Bounds on the restrained Roman domination number of a graph

Document Type : Original paper

Authors

Babol Noshirvani University of Technology

Abstract

A {\em Roman dominating function} on a graph $G$ is a function $f:V(G)\rightarrow \{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$. A {\em restrained Roman dominating} function $f$ is a Roman dominating function if the vertices with label 0 induce a subgraph with no isolated vertex. The weight of a restrained Roman dominating function is the value $\omega(f)=\sum_{u\in V(G)} f(u)$. The minimum weight of a restrained  Roman dominating function of $G$ is called the { \em restrained  Roman domination number} of $G$ and denoted by $\gamma_{rR}(G)$. In this paper we establish some sharp bounds for this parameter. 

Keywords

Main Subjects

References

[1] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999), no. 1, 61–69.
[2] G.S. Domke, J.H. Hattingh, M.A. Henning, and L.R. Markus, Restrained domination in graphs with minimum degree two, J. Combin. Math. Combin. Comput. 35 (2000), 239–254.
[3] , Restrained domination in trees, Discrete Math. 211 (2000), no. 1, 1–9.
[4] J.H. Hattingh and E.J. Joubert, An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree, Discrete Appl. Math. 157 (2009), no. 13, 2846–2858.
[5] , The product of the restrained domination numbers of a graph and its complement, Acta Math. Sinica, English Series 30 (2014), no. 3, 445–452.
[6] N. Jafari Rad and M. Krzywkowski, On the restrained Roman domination in graphs, Manuscript.
[7] R.L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Transactions on Combinatorics 4 (2015), no. 1, 1–17.
[8] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[9] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), 136–138. 
[10] D.B. West, Introduction to graph theory, vol. 2, Prentice hall Upper Saddle River, 2001.

Files

Share

How to cite

Statistics