Geodesic
A note on the double Roman domination number of graphs
Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 205-212
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2019.0212-18
Classification : 05C35, 05C69
Keywords: double Roman domination number; domination number; minimum degree 
@article{10_21136_CMJ_2019_0212_18,
     author = {Chen, Xue-Gang},
     title = {A note on the double {Roman} domination number of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {205--212},
     year = {2020},
     volume = {70},
     number = {1},
     doi = {10.21136/CMJ.2019.0212-18},
     mrnumber = {4078354},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0212-18/}
}
TY  - JOUR
AU  - Chen, Xue-Gang
TI  - A note on the double Roman domination number of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2020
SP  - 205
EP  - 212
VL  - 70
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0212-18/
DO  - 10.21136/CMJ.2019.0212-18
LA  - en
ID  - 10_21136_CMJ_2019_0212_18
ER  - 
%0 Journal Article
%A Chen, Xue-Gang
%T A note on the double Roman domination number of graphs
%J Czechoslovak Mathematical Journal
%D 2020
%P 205-212
%V 70
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0212-18/
%R 10.21136/CMJ.2019.0212-18
%G en
%F 10_21136_CMJ_2019_0212_18
Chen, Xue-Gang. A note on the double Roman domination number of graphs. Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 205-212. doi: 10.21136/CMJ.2019.0212-18

[1] Abdollahzadeh, H. Ahangar, Chellali, M., Sheikholeslami, S. M.: On the double Roman domination in graphs. Discrete Appl. Math. 232 (2017), 1-7. | DOI | MR | JFM

[2] Beeler, R. A., Haynes, T. W., Hedetniemi, S. T.: Double Roman domination. Discrete Appl. Math. 211 (2016), 23-29. | DOI | MR | JFM

[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 | MR | JFM

[4] McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two. J. Graph Theory 13 (1989), 749-762. | DOI | MR | JFM

[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 | MR | JFM

[7] ReVelle, C. S., Rosing, K. E.: Defendents imperium Romanum: a classical problem in military strategy. Am. Math. Mon. 107 (2000), 585-594. | DOI | MR | JFM

[8] Stewart, I.: Defend the Roman empire{!}. Sci. Amer. 281 (1999), 136-139. | DOI

Cité par Sources :