Bounds on signed total double Roman domination

Document Type : Original paper

Authors

1 Azarbaijan Shahid Madani University

2 Babol Noshirvani University of Technology

Abstract

A signed total double Roman dominating function (STDRDF) on {an} isolated-free graph $G=(V,E)$ is a function $f:V(G)\rightarrow\{-1,1,2,3\}$ such that (i) every vertex $v$ with $f(v)=-1$ has at least two neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, (ii) every vertex $v$ with $f(v)=1$ has at least one neighbor $w$ with $f(w)\geq2$ and (iii) $\sum_{u\in N(v)}f(u)\ge1$ holds for any vertex $v$. The weight of {an} STDRDF is the value $f(V(G))=\sum_{u\in V(G)}f(u).$ The signed total double Roman domination number $\gamma^t_{sdR}(G)$ is the minimum weight of an STDRDF on $G$. In this paper, we continue the study of the signed total double Roman domination in graphs and present some sharp bounds for this parameter.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Atapour, M. Chellali, and S.M. Sheikholeslami, Double Roman trees, Ars Combin. 145 (2019), 173–183.
[2] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A, Sci. 43 (2019), no. 3,
1081–1088.
[3] H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami, L. Volkmann, and Y. Zhao, Signed Roman edge domination numbers in graphs, J. Comb. Optim. 31 (2016), no. 1, 333–346.
[4] H. Abdollahzadeh Ahangar, L. Asgharsharghi, S.M. Sheikholeslami, and L. Volkmann, Signed mixed Roman domination numbers in graphs, J. Comb. Optim. 32 (2016), no. 1, 299–317.
[5] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[6] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Signed double Roman domination in graphs, Discrete Appl. Math. 257 (2019), 1–11.
[7] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Signed double Roman domination in graphs, Filomat 33 (2019), no. 1, 121–134.
[8] H. Abdollahzadeh Ahangar, M.A. Henning, C. Löwenstein, Y. Zhao, and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), no. 2, 241–255.
[9] H. Abdollahzadeh Ahangar, R. Khoeilar, L. Shahbazi, and S.M. Sheikholeslami, Signed total double Roman domination, Ars Combin. (to appea).
[10] H. Amjadi, J.and Yang, S. Nazari-Moghaddam, S.M. Sheikholeslami, and Z. Shao, Signed double Roman $k$-domination in graphs., Australas. J Comb. 72 (2018), 82–105.
[11] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[12] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. (to appear).
[13] 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 (in press).
[14] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. (in
press).
[15] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Structures of Domination in Graphs, (eds), T.W. haynes, S.T. hedetniemi and M.A. henning, ch. Varieties of Roman domination, Springer, 2021.
[16] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Topics in Domination in Graphs, (eds), T.W. haynes, S.T. hedetniemi and M.A. henning, ch. Roman domination in graphs, Springer, 2020.
[17] 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.
[18] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[19] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[20] D.B. West, Introduction to Graph Theory, Prentice Hall, USA, 2001.
[21] H. Yang, P. Wu, S. Nazari-Moghaddam, S.M. Sheikholeslami, X. Zhang, Z. Shao, and Y.Y. Tang, Bounds for signed double Roman k-domination in trees, RAIRO, Oper. Res. 53 (2019), no. 2, 627–643.
 
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 191-206

Files

Share

How to cite

Statistics