| Title:
|
A note on the double Roman domination number of graphs (English) |
| Author:
|
Chen, Xue-Gang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
70 |
| Issue:
|
1 |
| Year:
|
2020 |
| Pages:
|
205-212 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
double Roman domination number |
| Keyword:
|
domination number |
| Keyword:
|
minimum degree |
| MSC:
|
05C35 |
| MSC:
|
05C69 |
| idZBL:
|
07217129 |
| idMR:
|
MR4078354 |
| DOI:
|
10.21136/CMJ.2019.0212-18 |
| . |
| Date available:
|
2020-03-10T10:17:54Z |
| Last updated:
|
2022-04-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148050 |
| . |
| Reference:
|
[1] Abdollahzadeh, H. Ahangar, Chellali, M., Sheikholeslami, S. M.: On the double Roman domination in graphs.Discrete Appl. Math. 232 (2017), 1-7. Zbl 1372.05153, MR 3711941, 10.1016/j.dam.2017.06.014 |
| Reference:
|
[2] Beeler, R. A., Haynes, T. W., Hedetniemi, S. T.: Double Roman domination.Discrete Appl. Math. 211 (2016), 23-29. Zbl 1348.05146, MR 3515311, 10.1016/j.dam.2016.03.017 |
| Reference:
|
[3] Cockayne, E. J., jun., P. M. Dreyer, Hedetniemi, S. M., Hedetniemi, S. T.: Roman domination in graphs.Discrete Math. 278 (2004), 11-22. Zbl 1036.05034, MR 2035387, 10.1016/j.disc.2003.06.004 |
| Reference:
|
[4] McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two.J. Graph Theory 13 (1989), 749-762. Zbl 0708.05058, MR 1025896, 10.1002/jgt.3190130610 |
| Reference:
|
[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). |
| Reference:
|
[6] Reed, B. A.: Paths, stars, and the number three.Comb. Probab. Comput. 5 (1996), 277-295. Zbl 0857.05052, MR 1411088, 10.1017/S0963548300002042 |
| Reference:
|
[7] ReVelle, C. S., Rosing, K. E.: Defendents imperium Romanum: a classical problem in military strategy.Am. Math. Mon. 107 (2000), 585-594. Zbl 1039.90038, MR 1786232, 10.2307/2589113 |
| Reference:
|
[8] Stewart, I.: Defend the Roman empire{!}.Sci. Amer. 281 (1999), 136-139. 10.1038/scientificamerican1299-136 |
| . |
