Restrained roman domination in graphs

Document Type : National Conference on Labelings and Decompositions of Graphs

Authors

1 Department of Mathematics D.B.Jain College, Chennai 97 India

2 Department of Mathematics Sri Sairam Engineering College Chennai 44 India

Abstract

‎A \textit{Roman dominating function} (RDF) on a graph $G = (V,E)$ is‎ ‎defined to be a function $ f:V \rightarrow \lbrace 0,1,2\rbrace$‎ ‎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 set $S‎ ‎\subseteq V$ is a \textit{Restrained dominating set} if every vertex‎ ‎not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V‎ - ‎S$‎. ‎We define a \textit{Restrained Roman dominating function} on a‎ ‎graph $G = (V,E)$ to be a function $f‎ : ‎V \rightarrow \lbrace 0,1,2‎ ‎\rbrace$ 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$‎ ‎and at least one vertex $w$ for which $f(w) = 0$‎. ‎The \textit{weight}‎ ‎of a Restrained Roman dominating function is the value $f(V)= \sum _{u‎ ‎\in V} f(u)$‎. ‎The minimum weight of a Restrained Roman dominating‎ ‎function on a graph $G$ is called the Restrained Roman‎ ‎domination number of $G$ and denoted by $\gamma_{rR}(G)$‎. ‎In this‎ ‎paper‎, ‎we initiate a study of this parameter‎.

Keywords

Main Subjects


G‎. ‎Chartand and L‎. ‎Lesniak (2005). Graphs and Digraphs. ‎Fourth edition‎, ‎CRC Press‎, ‎Boca Raton‎, ‎FL. P‎. ‎Dankelmann‎, ‎J‎. ‎H‎. ‎Hattingh‎, ‎M‎. ‎A‎. ‎Henning and‎ ‎H‎. ‎C‎. ‎Swart (2006). ‎Trees with equal domination and Restrained ‎Domination numbers. J‎. ‎Global Optim.. 34, 597-607 G‎. ‎S‎. ‎Domke‎, ‎J‎. ‎H‎. ‎Hattingh‎, ‎S‎. ‎T‎. ‎Hedetniemi‎, ‎R‎. ‎C‎. ‎Laskar and L‎. ‎R‎. ‎Markus (1999). ‎Restrained domination in graphs. Discrete Math.. 203, 61-69 G‎. ‎S‎. ‎Domke‎, ‎J‎. ‎H‎. ‎Hattingh‎, ‎S‎. ‎T‎. ‎Hedetniemi and L‎. ‎R‎. ‎Markus (2009). ‎Restrained domination in trees. Discrete‎ ‎Math.. 211, 1-9 G‎. ‎S‎. ‎Domke‎, ‎J‎. ‎H‎. ‎Hattingh‎, ‎M‎. ‎A‎. ‎Henning and L‎. ‎R‎. ‎Markus (2000). ‎Restrained domination in graphs with minimum degree two. J‎. ‎Combin‎. ‎Math‎. ‎Combin‎. ‎Comput.. 35, 239-254 E‎. ‎Ebrahimi Targhi‎, ‎N‎. ‎Jafari Rad and L‎. ‎Volkmann (2011). ‎Unique response roman domination in graphs. Discrete Appl‎. ‎Math.. 159, 1110-1117 E‎. ‎J‎. ‎Cockayne‎, ‎P‎. ‎A‎. ‎Dreyer Jr.‎, ‎Sandra M‎. ‎Hedetniemi and S‎. ‎Hedetniemi (2004). ‎Roman domination in graphs. Discrete Math.. 278, 11-22 O‎. ‎Favaron‎, ‎H‎. ‎Karami‎, ‎R‎. ‎Khoeilar and S‎. ‎M‎. ‎Sheikholeslami (2009). ‎Note on the roman domination number of a graph. Discrete Math.. 309, 3447-3451 X‎. ‎Fu‎, ‎Y‎. ‎Yang and B‎. ‎Jiang (2009). ‎Roman domination in regular graphs. Discrete Math.. 309, 1528-1537 A‎. ‎Hansberg and L‎. ‎Volkmann (2009). ‎Upper bounds on the $k$-domination number and the $k$-roman domination number. Discrete Appl‎. ‎Math.. 157, 1634-1639 T‎. ‎W‎. ‎Haynes‎, ‎S‎. ‎T‎. ‎Hedetniemi and P‎. ‎J‎. ‎Slater ‎and ‎e‎ds. (1998). Fundamentals of domination in graphs. ‎Marcel Dekker‎, ‎Inc.‎, ‎New York. 208 T‎. ‎W‎. ‎Haynes‎, ‎S‎. ‎T‎. ‎Hedetniemi and P‎. ‎J‎. ‎Slater ‎and ‎‎eds. (1998). Domination in graphs; Advanced Topics. ‎Marcel Dekker‎, ‎Inc‎. ‎New York. M‎. ‎A‎. ‎Henning and S‎. ‎T‎. ‎Hedetniemi (2003). ‎Defending the roman empire-A new strategy. Discrete Math.. 266, 239-251 M‎. ‎A‎. ‎Henning (1999). ‎Graphs with large restrained domination number. Discrete Math.. 197/198, 415-429 M‎. ‎A‎. ‎Henning (2002). ‎A characterization of Roman trees. Discuss‎. ‎Math‎. ‎Graph Theory. 22 (2), 325-334 M‎. ‎A‎. ‎Henning (2003). ‎Defending the roman empire from multiple attacks. Discrete Math.. 271, 101-115 H.-M‎. ‎Xing‎, ‎Xin Chen and X.-G‎. ‎Chen‎ (2006). ‎A note on roman domination in graphs. Discrete Math.. 306, 3338-3340 N‎. ‎Jafari Rad and L‎. ‎Volkmann (2011). ‎On the roman bondage number of planar graphs. Graphs Combin.. 27, 531-538 N‎. ‎Jafari Rad and L‎. ‎Volkmann (2011). ‎Roman domination perfect graph. An‎. ‎Stiint‎. ‎Univ‎. ‎``Ovidius'' Constanta Ser‎. ‎Mat.. 19 (3), 167-174 T‎. ‎Kraner Sumenjak‎, ‎P‎. ‎Pavlic and A‎. ‎Tepeh (2012). ‎On the roman domination in the lexicographic products of graphs. Discrete Appl‎. ‎Math.. 160 (13-14), 2030-2036 C‎. ‎S‎. ‎ReVelle (1997). ‎Test your solution to ``Can you protect the Roman Empire?. John Hopkins Magazine. 49 (3), 70 C‎. ‎S‎. ‎ReVelle and K‎. ‎E‎. ‎Rosing (2000). ‎Defendens Romanum‎: ‎Imperium problem in military strategy. American Mathematical Monthly. 107 (7), 585-594 R‎. ‎R‎. ‎Rubalcaba and P‎. ‎J‎. ‎Slater (2007). ‎Roman domination influence parameters. Discrete Math.. 307, 3194-3200 P‎. ‎Roushini Leely Pushpam and T‎. ‎N‎. ‎M‎. ‎Malini Mai (2008). ‎On efficiently roman dominatable graphs. J‎. ‎Combin‎ ‎Math‎. ‎Combin‎. ‎Comput.. 67, 49-58 P‎. ‎Roushini Leely Pushpam and T‎. ‎N‎. ‎M‎. ‎Malini Mai (2009). ‎Edge roman domination in graphs. J‎. ‎Combin Math‎. ‎Combin‎. ‎Comput.. 69, 175-182 P‎. ‎Roushini Leely Pushpam and T‎. ‎N‎. ‎M‎. ‎Malini Mai (2011). ‎Weak roman domination in graphs. Discuss‎. ‎Math‎. ‎Graph Theory. 31, 115-128 P‎. ‎Roushini Leely Pushpam and T‎. ‎N‎. ‎M‎. ‎Malini Mai (2011). ‎Weak edge roman domination in graphs. Australas‎. ‎J‎. ‎Comb.. 51, 125-138 P‎. ‎Roushini Pushpam and T‎. ‎N‎. ‎M‎. ‎Malini Mai (2012). ‎Roman domination in unicyclic graphs. Journal of Discrete‎ ‎Mathematical Sciences and Cryptography. 15, 237-257 I‎. ‎Stewart (1999). ‎Defend the Roman Empire!. Scientific American. 281 (6), 136-138
  • Receive Date: 17 September 2013
  • Revise Date: 24 January 2014
  • Accept Date: 26 January 2014
  • Published Online: 01 March 2015