Total restrained Roman domination

Document Type : Original paper

Authors

1 Azarbaijan Shahid Madani University

2 Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

3 RWTH Aachen University

Abstract

Let $G$ be a graph with vertex set $V(G)$. A Roman dominating function  (RDF) on a graph $G$ is a function $f:V(G)\longrightarrow\{0,1,2\}$ such that every vertex $v$  with $f(v)=0$ is adjacent to a vertex  $u$ with $f(u)=2$. If $f$ is an RDF on $G$, then let $V_i=\{v\in V(G): f(v)=i\}$ for $i\in\{0,1,2\}$. An RDF $f$ is called a restrained (total) Roman dominating function if the subgraph induced by $V_0$  (induced by $V_1\cup V_2$) has no isolated vertex. A total and restrained Roman dominating function is a total restrained Roman  dominating function.  The total restrained Roman domination number $\gamma_{trR}(G)$ on a graph $G$ is the minimum weight of a total restrained Roman dominating function on the graph $G$. We initiate the study of total restrained Roman domination number and present several sharp bounds on $\gamma_{trR}G)$. In addition, we determine this parameter for some classes of graphs.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami, and M. Soroudi, On the total Roman domination number of graphs, Ars Combin. 150 (2020), 225–240.
[2] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Total Roman {2}-dominating functions in graphs, Discuss. Math. Graph Theory 42 (2022), no. 3, 937 – 958.
[3] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016), no. 2, 501–517.
[4] H. Abdollahzadeh Ahangar and S.R. Mirmehdipour, Bounds on the restrained Roman domination number of a graph, Commun. Comb. Optim. 1 (2016), no. 1, 75–82.
[5] A. Cabrera Martínez, S. Cabrera García, and A. Carríon García, Further results on the total Roman domination in graphs, Mathematics 8 (2020), no. 3, ID: 349.
[6] A. Cabrera Martínez, A. Martínez Arias, and M. Menendez Castillo, A characterization relating domination, semitotal domination and total Roman domination in trees, Commun. Comb. Optim. 6 (2021), no. 2, 197–209.
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, pp. 365–409.
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, pp. 273–307.
[10] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[11] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[12] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, WH Freeman, San Francisco, 1979.
[13] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
[14] D.-X. Ma, X.-G. Chen, and L. Sun, On total restrained domination in graphs, Czechoslovak Math. J. 55 (2005), no. 1, 165–173.
[15] R.L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4 (2015), no. 1, 1–17.
[16] F. Siahpour, H. Abdollahzadeh Ahangar, and S.M. Sheikholeslami, Some progress on the restrained Roman domination, Bull. Malays. Math. Sci. Soc. 44 (2021), no. 2, 733–751.
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 575-587

Files

Share

How to cite

Statistics