Restrained double Roman domatic number

Document Type : Original paper

Author

Lehrstuhl II fur Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

Let G be a graph with vertex set V(G). A double Roman dominating function (DRDF) on a graph G is a function f:V(G){0,1,2,3} having the property that if f(v)=0, then the vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w)=3, and if f(v)=1, then the vertex v mus have at least one neighbor u with f(u)2. If f is a DRDF on G, then let V0={vV(G):f(v)=0}. A restrained double Roman dominating function is a DRDF f having the property that the subgraph induced by V0 does not have an isolated vertex. A set {f1,f2,,fd} of distinct restrained double Roman dominating functions on G with the property that i=1dfi(v)3 for each vV(G) is called a restrained double Roman dominating family (of functions) on G. The maximum number of functions in a restrained double Roman dominating family on G is the restrained double Roman domatic number of G, denoted by drdR(G). We initiate the study of the restrained double Roman domatic number, and we present different sharp bounds on drdR(G). In addition, we determine this parameter for some classes of graphs.

Keywords

Main Subjects


[1] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29. https://doi.org/10.1016/j.dam.2016.03.017
[2] 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, p. 365–409.
[3] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Combin. 17 (2020), no. 3, 966–984.  https://doi.org/10.1016/j.akcej.2019.12.001
[4] 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, p. 273–307.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory 42 (2020), no. 3, 861–891.  https://doi.org/10.7151/dmgt.2313
[6] T.W Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[7] D.A. Mojdeh, I. Masoumi, and L. Volkmann, Restrained double Roman domination of a graph, RAIRO Oper. Res. 56 (2022), no. 4, 2293–2304.  https://doi.org/10.1051/ro/2022089
[8] O. Ore, Theory of Graphs, American Mathematical Society, 1962.
[9] D. Sitton, Maximum matchings in complete multipartite graphs, Int. J. Res. Undergrad. Math. Educ. 2 (1996), no. 1, 6–16.
[10] L. Volkmann, The double Roman domatic number of a graph, J. Combin. Math. Combin. Comput. 104 (2018), 205–215.