Restrained double Roman domatic number

Document Type : Original paper

Author

RWTH Aachen University

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)\longrightarrow\{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)\ge 2$. If $f$ is a DRDF on $G$, then let $V_0=\{v\in V(G): f(v)=0\}$. A restrained double Roman dominating function is a DRDF $f$ having the property that the subgraph induced by $V_0$ does not have an isolated vertex. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct restrained double Roman dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 3$ for each $v\in V(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 $d_{rdR}(G)$. We initiate the study of the restrained double Roman domatic number, and we present different sharp bounds on $d_{rdR}(G)$. In addition, we determine this parameter for some classes of graphs.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 23 January 2024

Files

Share

How to cite

Statistics