Czechoslovak Mathematical Journal, first online, pp. 1-8


A note on the double Roman domination number of graphs

Xue-gang Chen

Received April, 27, 2018.   Published online September 18, 2019.

Abstract:  For a graph $G=(V,E)$, a double Roman dominating function is a function $f\colon V\rightarrow\{0,1,2,3\}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must have at least one neighbor with $f(w)\geq2$. The weight of a double Roman dominating function $f$ is the sum $f(V)=\sum\nolimits_{v\in V}f(v)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by $\gamma_{\rm dR}(G)$. In this paper, we establish a new upper bound on the double Roman domination number of graphs. We prove that every connected graph $G$ with minimum degree at least two and $G\neq C_5$ satisfies the inequality $\gamma_{\rm dR}(G)\leq\lfloor\frac{13}{11}n\rfloor$. One open question posed by R. A. Beeler et al. has been settled.
Keywords:  double Roman domination number; domination number; minimum degree
Classification MSC:  05C69, 05C35
DOI:  10.21136/CMJ.2019.0212-18

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] H. Ahangar Abdollahzadeh, M. Chellali, S. M. Sheikholeslami: On the double Roman domination in graphs. Discrete Appl. Math. 232 (2017), 1-7. DOI 10.1016/j.dam.2017.06.014 | MR 3711941 | Zbl 1372.05153
[2] R. A. Beeler, T. W. Haynes, S. T. Hedetniemi: Double Roman domination. Discrete Appl. Math. 211 (2016), 23-29. DOI 10.1016/j.dam.2016.03.017 | MR 3515311 | Zbl 1348.05146
[3] E. J. Cockayne, P. M. Dreyer jun., S. M. Hedetniemi, S. T. Hedetniemi: Roman domination in graphs. Discrete Math. 278 (2004), 11-22. DOI 10.1016/j.disc.2003.06.004 | MR 2035387 | Zbl 1036.05034
[4] W. McCuaig, B. Shepherd: Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749-762. DOI 10.1002/jgt.3190130610 | MR 1025896 | Zbl 0708.05058
[5] B. A. Reed: Paths, Stars, and the Number Three: The Grunge. Research Report CORR 89-41, University of Waterloo, Department of Combinatorics and Optimization, Waterloo (1989).
[6] B. A. Reed: Paths, stars, and the number three. Comb. Probab. Comput. 5 (1996), 277-295. DOI 10.1017/S0963548300002042 | MR 1411088 | Zbl 0857.05052
[7] C. S. ReVelle, K. E. Rosing: Defendents imperium Romanum: a classical problem in military strategy. Am. Math. Mon. 107 (2000), 585-594. DOI 10.2307/2589113 | MR 1786232 | Zbl 1039.90038
[8] I. Stewart: Defend the Roman empire! Sci. Amer. 281 (1999), 136-139. DOI 10.1038/scientificamerican1299-136

Affiliations:   Xue-gang Chen, Department of Mathematics, North China Electric Power University, No. 2, Beinong road, Changping District, Beijing 102206, P. R. China, e-mail: gxcxdm@163.com


 
PDF available at: