Total double Roman domination in graphs

Document Type : Original paper

Authors

1 College of Science, East China University of Technology, Nanchang, P. R. China

2 RWTH Aachen University

3 University of Mazandaran

Abstract

Let $G$ be a simple graph with vertex set $V$. A double Roman dominating function (DRDF) on $G$ is a function $f:V\rightarrow\{0,1,2,3\}$ satisfying that if $f(v)=0$, then the vertex $v$ must be adjacent to at least two vertices assigned $2$ or one vertex assigned $3$ under $f$, whereas if $f(v)=1$, then the vertex $v$ must be adjacent to at least one vertex assigned $2$ or $3$. The weight of a DRDF $f$ is the sum $\sum_{v\in V}f(v)$. A total double Roman dominating function (TDRDF) on a graph $G$ with no isolated vertex is a DRDF $f$ on $G$ with the additional property that the subgraph of $G$ induced by the set $\{v\in V:f(v)\ne0\}$ has no isolated vertices. The total double Roman domination number $\gamma_{tdR}(G)$ is the minimum weight of a TDRDF on $G$. In this paper, we give several relations between the total double Roman domination number of a graph and other domination parameters and we determine the total double Roman domination number of some classes of graphs.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[2] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016), 501–517.
[3] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami, and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin. 69 (2017), no. 2, 271–285.
[4] J. Amjadi, S.M. Sheikholeslami, and M. Soroudi, Nordhaus-Gaddum bounds for total Roman domination, J. Comb. Optim. 35 (2018), no. 1, 126–133.
[5] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[6] C. Bujtás and S. Klavžar, Improved upper bounds on the domination number of graphs with minimum degree at least five, Graphs Combin. 32 (2016), no. 2, 511–519.
[7] J. Cyman, M. Dettlaff, M.A. Henning, M. Lema´nska, and J. Raczek, Total domination versus domination in cubic graphs, Graphs Combin. 34 (2018), no. 1, 261–276.
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[9] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), no. 1, 32–63.
[10] M.A. Henning and A. Yeo, Total domination in graphs, Springer, 2013.
[11] M. Lemańska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24 (2004), no. 2, 165–169.
[12] N.J. Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019), no. 1, 41–53.
[13] Z. Shao, J. Amjadi, S.M. Sheikholeslami, and M. Valinavaz, On the total double Roman domination, IEEE Access 7 (2019), 52035–52041.
[14] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77.
[15] X. Zhang, Z. Li, H. Jiang, and Z. Shao, Double Roman domination in trees, Inform. Process. Lett. 134 (2018), 31–34.
Communications in Combinatorics and Optimization
Volume 5, Issue 1
June 2020
Pages 27-39

Files

Share

How to cite

Statistics