Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
double Roman domination number; domination number; minimum degree
double Roman domination number; domination number; minimum degree
Summary:
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)\geq 2$. 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.
References:
[1] Abdollahzadeh, H. Ahangar, Chellali, M., Sheikholeslami, S. M.: 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] Beeler, R. A., Haynes, T. W., Hedetniemi, S. T.: Double Roman domination. Discrete Appl. Math. 211 (2016), 23-29. DOI 10.1016/j.dam.2016.03.017 | MR 3515311 | Zbl 1348.05146
[3] Cockayne, E. J., jun., P. M. Dreyer, Hedetniemi, S. M., Hedetniemi, S. T.: Roman domination in graphs. Discrete Math. 278 (2004), 11-22. DOI 10.1016/j.disc.2003.06.004 | MR 2035387 | Zbl 1036.05034
[4] McCuaig, W., Shepherd, B.: 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] Reed, B. A.: Paths, Stars, and the Number Three: The Grunge. Research Report CORR 89-41, University of Waterloo, Department of Combinatorics and Optimization, Waterloo (1989).
[6] Reed, B. A.: Paths, stars, and the number three. Comb. Probab. Comput. 5 (1996), 277-295. DOI 10.1017/S0963548300002042 | MR 1411088 | Zbl 0857.05052
[7] ReVelle, C. S., Rosing, K. E.: 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] Stewart, I.: Defend the Roman empire{!}. Sci. Amer. 281 (1999), 136-139. DOI 10.1038/scientificamerican1299-136
Search
Partner of
