An upper bound on triple Roman domination

Document Type : Original paper

Authors

1 Azarbaijan Shahid Madani University

2 Babol Noshirvani University of Technology

3 Guangzhou University

Abstract

For a graph $G=(V,E)$, a triple Roman dominating function (3RD-function) is a function $f:V\to \{0,1,2,3,4\}$ having the property that (i) if $f(v)=0$ then $v$ must have either one neighbor $u$ with $f(u)=4$, or two neighbors $u,w$ with $f(u)+f(w)\ge 5$ or three neighbors $u,w,z$ with $f(u)=f(w)=f(z)=2$, (ii) if $f(v)=1$ then $v$ must have one neighbor $u$ with $f(u)\ge 3$ or two neighbors $u,w$ with $f(u)=f(w)=2$, and (iii) if $f(v)=2$ then $v$ must have one neighbor $u$ with $f(u)\ge 2$. The weight of a 3RDF $f$ is the sum $f(V)=\sum_{v\in V} f(v)$, and the minimum weight of a 3RD-function on $G$ is the triple Roman domination number of $G$, denoted by $\gamma_{[3R]}(G)$. In this paper, we prove that for any connected graph $G$ of order $n$ with minimum degree at least two,  $\gamma_{[3R]}(G)\leq \frac{3n}{2}$.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M.P. Álvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Appl. Math. Comput. 391 (2021), ID: 125444.
[2] J. Arquilla and H. Fredricksen, “ Graphing” an optimal grand strategy, Military Operations Research 1 (1995), 3–17.
[3] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[4] 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.
[5] 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. 115 (2020), 141–171.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138. 
 
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 505-511

Files

Share

How to cite

Statistics