Research article

A note on the bounds of Roman domination numbers

  • Received: 20 December 2020 Accepted: 25 January 2021 Published: 02 February 2021
  • MSC : 05C69

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2019) PDF downloads(165) Cited by(0)

Article outline

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog