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→{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)≥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)≥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)≥2. The weight of a 3RDF f is the sum f(V)=∑v∈Vf(v), and the minimum weight of a 3RD-function on G is the triple Roman domination number of G, denoted by γ[3R](G). In this paper, we prove that for any connected graph G of order n with minimum degree at least two,  γ[3R](G)≤3n2.

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