Quasi total double Roman domination in trees

Document Type : Original paper

Authors

1 Clinical Research Development Unit of Rouhani Hospital, Babol University of Medical Sciences, Babol 4717647745, Iran

2 Department of Mathematics, Prince Sattam bin Abdulaziz University, Alkharj 11991, Saudi Arabia

3 Department of Computer Science, College of Arts and Science, Prince Sattam bin Abdul Aziz University, Wadi Ad-Dwasir 11991, Saudi Arabia

4 RWTH Aachen University, 52056 Aachen, Germany

Abstract

A quasi total double Roman dominating function (QTDRD-function) on a graph $G=(V(G),E(G))$ is a function $f:V(G)\longrightarrow\{0,1,2,3\}$ having the property that \textrm{(i)} if $f(v)=0$, then vertex $v$ must have at least two
neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$; \textrm{(ii)} if $f(v)=1$, then vertex $v$ has at least one neighbor $w$ with $f(w)\geq2$, and \textrm{(iii)} if $x$ is an isolated vertex in the subgraph induced by the set of vertices assigned non-zero values, then $f(x)=2$. The weight of a QTDRD-function $f$ is the sum of its function values over the whole vertices, and the quasi total double Roman domination number $\gamma_{qtdR}(G)$ equals the minimum weight of a QTDRD-function on $G$. In this paper, we show that for any tree $T$ of order $n\ge 4$, $\gamma_{qtdR}(T)\le n+\frac{s(T)}{2}$, where $s(T)$ is the number of support vertices of $T$,  that improves a known bound.

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] S. Cabrera García, A.C. Martínez, and I.G. Yero, Quasi-total Roman domination in graphs, Results Math. 74 (2019), no. 4, Article number 173. https://doi.org/10.1007/s00025–019–1097–5
[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, p. 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.  https://doi.org/10.1016/j.akcej.2019.12.001
[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, p. 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.  https://doi.org/10.1016/j.disc.2003.06.004
[7] N. Ebrahimi, J. Amjadi, M. Chellali, and S.M. Sheikholeslami, Quasi-total Roman reinforcement in graphs, AKCE Int. J. Graphs Comb. 20 (2023), no. 1, 1–8.  https://doi.org/10.1080/09728600.2022.2158051
[8] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.  https://doi.org/10.22049/cco.2019.26484.1118
[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 43 (2023), no. 4, 1033–1061.  https://doi.org/10.7151/dmgt.2417
[10] S. Kosari, S. Babaei, J. Amjadi, M. Chellali, and S.M. Sheikholeslami, Bounds on quasi total double roman domination in graphs, (Submitted).
[11] S. Kosari, S. Babaei, J. Amjadi, M. Chellali, and S.M. Sheikholeslami, Quasi total double Roman domination in graphs, (Submitted).
[12] A.C. Martínez, J.C. Hernández-Gómez, and J.M. Sigarreta, On the quasi-total Roman domination number of graphs, Mathematics 9 (2021), no. 21, Article number 2823.  https://doi.org/10.3390/math9212823
[13] Z. Shao, J. Amjadi, S.M. Sheikholeslami, and M. Valinavaz, On the total double Roman domination, IEEE Access 7 (2019), 52035–52041.  https://doi.org/10.1109/ACCESS.2019.2911659
[14] A. Teymourzadeh and D.A. Mojdeh, Covering total double Roman domination in graphs, Commun. Comb. Optim. 8 (2023), no. 1, 115–125.  https://doi.org/10.22049/cco.2021.27443.1265
[15] M. Vikas and P. Venkata Subba Reddy, Algorithmic aspects of quasi-total Roman domination in graphs, Commun. Comb. Optim. 7 (2022), no. 1, 93–104.  https://doi.org/10.22049/cco.2021.27126.1200
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 159-168

Files

Share

How to cite

Statistics