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)⟶{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 Vi={v∈V(G):f(v)=i} for i∈{0,1,2}. An RDF f is called a restrained (total) Roman dominating function if the subgraph induced by V0  (induced by V1∪V2) has no isolated vertex. A total and restrained Roman dominating function is a total restrained Roman  dominating function.  The total restrained Roman domination number γ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 γtrRG). 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