Let $ G $ be a graph with vertex set $ V $. A function $ f $ : $ V\to \{-1, 0, 2\} $ is called a Roman balanced dominating function (RBDF) of $ G $ if $ \sum_{u\in N_G[v]}f(u) = 0 $ for each vertex $ v\in V $. The maximum (resp. minimum) Roman balanced domination number $ \gamma^{M}_{Rb}(G) $ (resp. $ \gamma^{m}_{Rb}(G) $) is the maximum (resp. minimum) value of $ \sum_{v\in V} f(v) $ among all Roman balanced dominating functions $ f $. A graph $ G $ is called $ Rd $-balanced if $ \gamma^{M}_{Rb}(G) = \gamma^{m}_{Rb}(G) = 0 $. In this paper, we obtain several upper and lower bounds on $ \gamma^{M}_{Rb}(G) $ and $ \gamma^{m}_{Rb}(G) $ and further determine several classes of $ Rd $-balanced graphs.
Citation: Mingyu Zhang, Junxia Zhang. On Roman balanced domination of graphs[J]. AIMS Mathematics, 2024, 9(12): 36001-36011. doi: 10.3934/math.20241707
Let $ G $ be a graph with vertex set $ V $. A function $ f $ : $ V\to \{-1, 0, 2\} $ is called a Roman balanced dominating function (RBDF) of $ G $ if $ \sum_{u\in N_G[v]}f(u) = 0 $ for each vertex $ v\in V $. The maximum (resp. minimum) Roman balanced domination number $ \gamma^{M}_{Rb}(G) $ (resp. $ \gamma^{m}_{Rb}(G) $) is the maximum (resp. minimum) value of $ \sum_{v\in V} f(v) $ among all Roman balanced dominating functions $ f $. A graph $ G $ is called $ Rd $-balanced if $ \gamma^{M}_{Rb}(G) = \gamma^{m}_{Rb}(G) = 0 $. In this paper, we obtain several upper and lower bounds on $ \gamma^{M}_{Rb}(G) $ and $ \gamma^{m}_{Rb}(G) $ and further determine several classes of $ Rd $-balanced graphs.
| [1] |
H. Ahangar, M. Alvarez, M. Chellali, S. Sheikholeslami, J. Valenzuela-Tripodoro, Triple Roman domination in graphs, Appl. Math. Comput., 391 (2021), 12544. https://doi.org/10.1016/j.amc.2020.125444 doi: 10.1016/j.amc.2020.125444
|
| [2] |
H. Ahangar, M. Chellali, S. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Comput., 354 (2020), 124617. https://doi.org/10.1016/j.amc.2019.124617 doi: 10.1016/j.amc.2019.124617
|
| [3] |
H. Ahangar, M. Henning, V. Samodivkin, I. Yero, Total Roman domination in graphs, Appl. Anal. Discre. Math., 10 (2016), 501–517. https://doi.org/10.2298/AADM160802017A doi: 10.2298/AADM160802017A
|
| [4] |
H. Ahangar, M. Henning, C. Lowenstein, Y. Zhao, V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim., 27 (2014), 241–255. https://doi.org/10.1007/s10878-012-9500-0 doi: 10.1007/s10878-012-9500-0
|
| [5] |
A. Alhevaz, M. Darkooti, H. Rahbani, Y. Shang, Strong equality of perfect Roman and weak Roman domination in trees, Mathematics, 7 (2019), 997. https://doi.org/10.3390/math7100997 doi: 10.3390/math7100997
|
| [6] |
J. Amjadi, S. Sheikholeslami, L. Volkmann, Global rainbow domination in graphs, Miskolc Math. Notes, 17 (2016), 749–759. https://doi.org/10.18514/MMN.2016.1267 doi: 10.18514/MMN.2016.1267
|
| [7] |
M. Atapour, S. Sheikholeslami, L. Volkmann, Global Roman domination in trees, Graphs Comb., 31 (2015), 813–825. https://doi.org/10.1007/s00373-014-1415-3 doi: 10.1007/s00373-014-1415-3
|
| [8] |
G. Atílio, Roman domination and independent Roman domination on graphs with maximum degree three, Discret. Appl. Math., 348 (2024), 260–278. https://doi.org/10.1016/j.dam.2024.02.006 doi: 10.1016/j.dam.2024.02.006
|
| [9] | E. Cockayne, Jr. Dreyer, S. Hedetniemi, S. Hedetniemi, Roman domination in graphs, Discret. Math., 278 (2004), 11–22. http://doi.org/10.1016/j.disc.2003.06.004 |
| [10] |
M. Henning, W. Klostermeyer, G. MacGillivray, Perfect Roman domination in trees, Discret. Appl. Math., 236 (2018), 234–245. https://doi.org/10.1016/j.dam.2017.10.027 doi: 10.1016/j.dam.2017.10.027
|
| [11] |
K. Mann, H. Fernau, Perfect Roman domination: Aspects of enumeration and parameterization, Comb. Algori., 14764 (2024), 354–368. https://doi.org/10.1007/978-3-031-63021-7_27 doi: 10.1007/978-3-031-63021-7_27
|
| [12] |
J. Padamutham, V. Palagiri, Complexity aspects of variants of independent Roman domination in graphs, Bull. Iran. Math. Soc., 47 (2021), 1715–1735. https://doi.org/10.1007/s41980-020-00468-5 doi: 10.1007/s41980-020-00468-5
|
| [13] |
F. Pour, H. Ahangar, M. Chellali, S. Sheikholeslami, Global triple Roman dominating function, Discret. Appl. Math., 314 (2022), 228–237. https://doi.org/10.1016/j.dam.2022.02.015 doi: 10.1016/j.dam.2022.02.015
|
| [14] |
P. Pushpam, S. Padmapriea, Global Roman domination in graphs, Discret. Appl. Math., 200 (2016), 176–185. https://doi.org/10.1016/j.dam.2015.07.014 doi: 10.1016/j.dam.2015.07.014
|
| [15] |
J. Raczek, J. Cyman, Weakly connected Roman domination in graphs, Discret. Appl. Math., 267 (2019), 151–159. https://doi.org/10.1016/j.dam.2019.05.002 doi: 10.1016/j.dam.2019.05.002
|
| [16] |
J. Shao, P. Wu, H. Jiang, Z. Li, J. Žerovnik, X. Zhang, Discharging approach for double Roman domination in graphs, IEEE Access, 6 (2018), 63345–63351. https://doi.org/10.1109/ACCESS.2018.2876460 doi: 10.1109/ACCESS.2018.2876460
|
| [17] | I. Stewart, Defend the Roman empire!, Sci. Am., 281 (1999), 136–138. https://doi.org/10.1038/scientificamerican1299-136 |
| [18] |
B. Xu, T. Lan, J. Zhang, M. Zheng, On the balanced cycle domination of graphs, AKCE Inter. J. Graph Comb., 20 (2022), 47–51. https://doi.org/10.1080/09728600.2022.2156309 doi: 10.1080/09728600.2022.2156309
|
| [19] |
B. Xu, W. Sun, S. Li, On the balanced domination of graphs, Czech. Math. J., 71 (2021), 933–946. https://doi.org/10.21136/CMJ.2021.0055-20 doi: 10.21136/CMJ.2021.0055-20
|
Figures(2)
Mingyu Zhang, Junxia Zhang. On Roman balanced domination of graphs[J]. AIMS Mathematics, 2024, 9(12): 36001-36011. doi: 10.3934/math.20241707
DownLoad: