Covering total double Roman domination in graphs

Document Type : Original paper

Authors

1 Department of Mathematics, University of Mazandaran, Babolsar, Iran

2 Departtment of Mathematics, University of Mazandaran

Abstract

For a graph $G$ with no isolated vertex, a covering total double Roman dominating function ($CTDRD$ function) $f$ of $G$ is a total double Roman dominating function ($TDRD$ function) of $G$ for which the set $\{v\in V(G)| f(v)\ne 0\}$ is a vertex cover set. The covering total double Roman domination number $\gamma_{ctdR}(G)$ equals the minimum weight of an $CTDRD$ function on $G$. An $CTDRD$ function on $G$ with weight $\gamma_{ctdR} (G)$ is called a $\gamma_{ctdR} (G)$-function. In this paper, the graphs $G$ with small $\gamma_{ctdR} (G)$ are characterised. We show that the decision problem associated with $CTDRD$ is $NP$-complete even when restricted to planer graphs with maximum degree at most four. We then show that for every graph $G$ without isolated vertices, $\gamma_{oitR}(G)<\gamma_{ctdR}(G)< 2\gamma_{oitR}(G)$ and for every tree $T$, $2\beta(T)+1\leq \gamma_{ctdR}(T)\leq4\beta(T)$, where $\gamma_{oitR}(G)$ and $\beta(T)$ are the outer independent total Roman domination number of $G$, and the minimum vertex cover number of $T$ respectively. Moreover we investigate the $\gamma_{ctdR}$ of corona of two graphs.

Keywords

Main Subjects

References

[1] 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.
[2] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman and Co. New York, USA, 1979.
[8] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.
[9] G. Hao, Z. Xie, S.M. Sheikholeslami, and M. Hajjari, Bounds on the total double Roman domination number of graphs, Discuss. Math. Graph Theory (in press).
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[11] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[12] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019), no. 1, 41–53.
[13] R. Khoeilar, M. Chellali, H. Karami, and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019), 159-167.
14] A.C. Martínez, D. Kuziak, and I.G. Yero, Outer-independent total Roman domination in graphs, Discrete Appl. Math. 269 (2019), 107–119.
[15] D.A. Mojdeh, A. Parsian, and I. Masoumi, Characterization of double Roman trees, Ars Combin. (to appear).
[16] D.A. Mojdeh, B. Samadi, Z. Shao, and I.G. Yero, On the outer independent double Roman domination number, Bull. Iran. Math. Soc. (in press).
[17] A. Teymourzadeh and D.A. Mojdeh, Upper bounds for covering total double Roman domination, TWMS J. App. and Eng. Math. (in press).
[18] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 115-125

Files

Share

How to cite

Statistics