Let $ G $ be a graph and $ f: V(G) \rightarrow \{0, 1, 2\} $ be a mapping. $ f $ is said to be a Roman dominating function of $ G $ if every vertex $ u $ for which $ f(u) = 0 $ is adjacent to at least one vertex $ v $ for which $ f(v) = 2 $. The weight $ w(f) $ of a Roman dominating function $ f $ is the value $ w(f) = \sum_{u \in V(G)}f(u) $, and the minimum weight of a Roman dominating function is the Roman domination number $ \gamma_R(G) $. $ f $ is said to be a Roman $ \{2\} $-dominating function of $ G $ if $ \sum_{v\in N(u)}f(v)\geq 2 $ for every vertex $ u $ with $ f(u) = 0 $, where $ N(u) $ is the set of neighbors of $ u $ in $ G $. The weight of a Roman {2}-dominating function $ f $ is the sum $ \sum_{v\in V}f(v) $ and the minimum weight of a Roman {2}-dominating function is the Roman {2}-domination number $ \gamma_{\{R2\}}(G) $. Chellali et al. (2016) proved that $ \gamma_{R}(G)\geq\frac{\Delta+1}{\Delta}\gamma(G) $ for every nontrivial connected graph $ G $ with maximum degree $ \Delta $. In this paper, we generalize this result on nontrivial connected graph $ G $ with maximum degree $ \Delta $ and minimum degree $ \delta $. We prove that $ \gamma_{R}(G)\geq\frac{\Delta+2\delta}{\Delta+\delta}\gamma(G) $, which also implies that $ \frac{3}{2}\gamma(G)\leq\gamma_{R}(G)\leq 2\gamma(G) $ for any nontrivial regular graph. Moreover, we prove that $ \gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $ for every graph $ G $ and there exists a graph $ I_k $ such that $ \gamma_{\{R2\}}(I_k) = k $ and $ \gamma_{R}(I_k) = 2k-1 $ for any integer $ k\geq2 $.
Citation: Zepeng Li. A note on the bounds of Roman domination numbers[J]. AIMS Mathematics, 2021, 6(4): 3940-3946. doi: 10.3934/math.2021234
Let $ G $ be a graph and $ f: V(G) \rightarrow \{0, 1, 2\} $ be a mapping. $ f $ is said to be a Roman dominating function of $ G $ if every vertex $ u $ for which $ f(u) = 0 $ is adjacent to at least one vertex $ v $ for which $ f(v) = 2 $. The weight $ w(f) $ of a Roman dominating function $ f $ is the value $ w(f) = \sum_{u \in V(G)}f(u) $, and the minimum weight of a Roman dominating function is the Roman domination number $ \gamma_R(G) $. $ f $ is said to be a Roman $ \{2\} $-dominating function of $ G $ if $ \sum_{v\in N(u)}f(v)\geq 2 $ for every vertex $ u $ with $ f(u) = 0 $, where $ N(u) $ is the set of neighbors of $ u $ in $ G $. The weight of a Roman {2}-dominating function $ f $ is the sum $ \sum_{v\in V}f(v) $ and the minimum weight of a Roman {2}-dominating function is the Roman {2}-domination number $ \gamma_{\{R2\}}(G) $. Chellali et al. (2016) proved that $ \gamma_{R}(G)\geq\frac{\Delta+1}{\Delta}\gamma(G) $ for every nontrivial connected graph $ G $ with maximum degree $ \Delta $. In this paper, we generalize this result on nontrivial connected graph $ G $ with maximum degree $ \Delta $ and minimum degree $ \delta $. We prove that $ \gamma_{R}(G)\geq\frac{\Delta+2\delta}{\Delta+\delta}\gamma(G) $, which also implies that $ \frac{3}{2}\gamma(G)\leq\gamma_{R}(G)\leq 2\gamma(G) $ for any nontrivial regular graph. Moreover, we prove that $ \gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1 $ for every graph $ G $ and there exists a graph $ I_k $ such that $ \gamma_{\{R2\}}(I_k) = k $ and $ \gamma_{R}(I_k) = 2k-1 $ for any integer $ k\geq2 $.
[1] | B. Brešar, M. A. Henning, D. F. Rall, Rainbow domination in graphs, Taiwan. J. Math., 12 (2008), 213–225. doi: 10.11650/twjm/1500602498 |
[2] | A. Cabrera-Martínez, I. G. Yero, Constructive characterizations concerning weak Roman domination in trees, Discrete Appl. Math., 284 (2020), 384–390. doi: 10.1016/j.dam.2020.03.058 |
[3] | E. W. Chambers, B. Kinnersley, N. Prince, D. B. West, Extremal problems for Roman domination, SIAM J. Discrete Math., 23 (2009), 1575–1586. doi: 10.1137/070699688 |
[4] | M. Chellali, T. W. Haynes, S. T. Hedetniemi, Lower bounds on the Roman and independent Roman domination numbers, Appl. Anal. Discrete Math., 10 (2016), 65–72. doi: 10.2298/AADM151112023C |
[5] | M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. A. McRae, Roman {2}-domination, Discrete Appl. Math., 204 (2016), 22–28. doi: 10.1016/j.dam.2015.11.013 |
[6] | E. J. Cockayne, P. A. Dreyer Jr, S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278 (2004), 11–22. doi: 10.1016/j.disc.2003.06.004 |
[7] | O. Favaron, H. Karami, R. Khoeilar, S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309 (2009), 3447–3451. doi: 10.1016/j.disc.2008.09.043 |
[8] | W. Goddard, M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory, 40 (2002), 1–25. doi: 10.1002/jgt.10027 |
[9] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs: Advanced Topics, New York: Marcel Dekker, 1998. |
[10] | Z. P. Li, E. Q. Zhu, Z. H. Shao, J. Xu, On dominating sets of maximal outerplanar and planar graphs, Discrete Appl. Math., 198 (2016), 164–169. doi: 10.1016/j.dam.2015.06.024 |
[11] | Z. P. Li, Z. H. Shao, J. Xu, Weak {2}-domination number of Cartesian products of cycles, J. Comb. Optim., 35 (2018), 75–85. doi: 10.1007/s10878-017-0157-6 |
[12] | M. Liedloff, T. Kloks, J. Liu, S. L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math., 156 (2008), 3400–3415. doi: 10.1016/j.dam.2008.01.011 |
[13] | C. J. Liu, A note on domination number in maximal outeplanar graphs, Discrete Appl. Math., 293 (2021), 90–94. doi: 10.1016/j.dam.2021.01.021 |
[14] | P. Wu, Z. P. Li, Z. H. Shao, S. M. Sheikholeslami, Trees with equal Roman {2}-domination number and independent Roman 2-domination number, RAIRO-Oper. Res., 53 (2019), 389–400. doi: 10.1051/ro/2018116 |
[15] | E. Q. Zhu, Z. H. Shao, Extremal problems on weak Roman domination number, Inf. Process. Lett., 138 (2018), 12–18. doi: 10.1016/j.ipl.2018.05.009 |