Let $ G = (V, E) $ be a simple graph with vertex set $ V $ and edge set $ E $, and let $ f $ be a function $ f:V\mapsto \{0, 1, 2\} $. A vertex $ u $ with $ f(u) = 0 $ is said to be undefended with respect to $ f $ if it is not adjacent to a vertex with positive weight. The function $ f $ is a weak Roman dominating function (WRDF) if each vertex $ u $ with $ f(u) = 0 $ is adjacent to a vertex $ v $ with $ f(v) > 0 $ such that the function $ f_{u}:V\mapsto \{0, 1, 2\} $, defined by $ f_{u}(u) = 1 $, $ f_{u}(v) = f(v)-1 $ and $ f_{u}(w) = f(w) $ if $ w\in V-\{u, v\} $, has no undefended vertex. The weight of $ f $ is $ w(f) = \sum_{v\in V}f(v) $. The weak Roman domination number, denoted $ \gamma_{r}(G) $, is the minimum weight of a WRDF in G. The domination number, denoted $ \gamma(G) $, is the minimum cardinality of a dominating set in $ G $. In this paper, we give some sufficient conditions for a tree to have its weak Roman domination number be equal to its domination number plus 1 ($ \gamma_{r}(T) = \gamma(T)+1 $) by recursion and construction.
Citation: Jian Yang, Yuefen Chen, Zhiqiang Li. Some sufficient conditions for a tree to have its weak Roman domination number be equal to its domination number plus 1[J]. AIMS Mathematics, 2023, 8(8): 17702-17718. doi: 10.3934/math.2023904
Let $ G = (V, E) $ be a simple graph with vertex set $ V $ and edge set $ E $, and let $ f $ be a function $ f:V\mapsto \{0, 1, 2\} $. A vertex $ u $ with $ f(u) = 0 $ is said to be undefended with respect to $ f $ if it is not adjacent to a vertex with positive weight. The function $ f $ is a weak Roman dominating function (WRDF) if each vertex $ u $ with $ f(u) = 0 $ is adjacent to a vertex $ v $ with $ f(v) > 0 $ such that the function $ f_{u}:V\mapsto \{0, 1, 2\} $, defined by $ f_{u}(u) = 1 $, $ f_{u}(v) = f(v)-1 $ and $ f_{u}(w) = f(w) $ if $ w\in V-\{u, v\} $, has no undefended vertex. The weight of $ f $ is $ w(f) = \sum_{v\in V}f(v) $. The weak Roman domination number, denoted $ \gamma_{r}(G) $, is the minimum weight of a WRDF in G. The domination number, denoted $ \gamma(G) $, is the minimum cardinality of a dominating set in $ G $. In this paper, we give some sufficient conditions for a tree to have its weak Roman domination number be equal to its domination number plus 1 ($ \gamma_{r}(T) = \gamma(T)+1 $) by recursion and construction.
| [1] |
I. Stewart, Defend the Roman Empire, Sci. Am., 281 (1999), 136–138. https://doi.org/10.1038/scientificamerican1299-136 doi: 10.1038/scientificamerican1299-136
|
| [2] |
E. J. Cockayne, P. A. Jr. Dreyer, S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs, Disc. Math., 278 (2004), 11–22. https://doi.org/10.1016/j.disc.2003.06.004 doi: 10.1016/j.disc.2003.06.004
|
| [3] |
A. Klobučar, I. Puljić, Roman domination number on cardinal product of paths and cycles, Croat. Oper. Res. Rev., 6 (2015), 71–78. https://doi.org/10.17535/crorr.2015.0006 doi: 10.17535/crorr.2015.0006
|
| [4] |
M. A. Henning, S. T. Hedetniemi, Defending the Roman Empire-A new strategy, Discrete Math., 266 (2003), 239–251. https://doi.org/10.1016/S0012-365X(02)00811-7 doi: 10.1016/S0012-365X(02)00811-7
|
| [5] |
R. Hernández-Ortiz, L. P. Montejano, J. A. Rodríguez-Velázquez, Weak Roman domination in rooted product graphs, AIMS Math., 6 (2021), 3641–3653. https://doi.org/10.3934/math.2021217 doi: 10.3934/math.2021217
|
| [6] | J. Yang, J. L. Song, Trees T with weak Roman domination number being equal to domination number, Mathematics in Practice and Theory (in Chinese), 43 (2013), 134–140. |
| [7] | J. Yang, Z. Q. Li, Some properties of weak Roman graph and weak Roman domination in graphs, Chin. J. of Eng. Math. (in Chinese), 39 (2022), 621–630. |
| [8] |
F. N. Pour, H. A. Ahangar, M. Chellali, S. M. Sheikholeslami, Global triple Roman dominating function, Discrete Appl. Math., 314 (2022), 228–237. https://doi.org/10.1016/j.dam.2022.02.015 doi: 10.1016/j.dam.2022.02.015
|
| [9] |
Z. Li, A note on the bounds of Roman domination numbers, AIMS Math., 6 (2021), 3940–3946. https://doi.org/10.3934/math.2021234 doi: 10.3934/math.2021234
|
| [10] |
M. Chellali, T. W. Haynes, S. T. Hedetniemi, Roman and total domination, Quaest. Math., 38 (2015), 749–757. https://doi.org/10.2989/16073606.2015.1015647 doi: 10.2989/16073606.2015.1015647
|
| [11] |
Z. Du, A. A. S. A. Jamri, R. Hasni, D. A. Mojdeh, Maximal first Zagreb index of trees with given Roman domination number, AIMS Math., 7 (2022), 11801–11812. https://doi.org/10.3934/math.2022658 doi: 10.3934/math.2022658
|
| [12] |
S. C. García, A. C. Martínez, I. G. Yero, Quasi-total Roman domination in graphs, Results Math., 74 (2019), 173. https://doi.org/10.1007/s00025-019-1097-5 doi: 10.1007/s00025-019-1097-5
|
| [13] |
P. R. L. Pushpam, S. Padmapriea, Global Roman domination in graphs, Discrete Appl. Math., 200 (2016), 176–185. https://doi.org/10.1016/j.dam.2015.07.014 doi: 10.1016/j.dam.2015.07.014
|
| [14] |
H. A. Ahangar, M. A. Henning, V. Samodivkin, I. G. Yero, Total Roman domination in graphs, Appl. Anal. Discr. Math., 10 (2016), 501–517. https://doi.org/10.2298/AADM160802017A doi: 10.2298/AADM160802017A
|
| [15] |
J. Amjadi, S. M. Sheikholeslami, M. Soroudi, Nordhaus-Gaddum bounds for total Roman domination, J. Comb. Optim., 35 (2018), 126–133. https://doi.org/10.1007/s10878-017-0158-5 doi: 10.1007/s10878-017-0158-5
|
| [16] | G. Gunther, B. L. Hartnell, L. Markus, D. Rall, Graphs with unique minimum domination sets, Congressus Numerantium, 101 (1994), 55–63. |
| [17] |
Z. Gu, J. X. Meng, Z. Zhang, J. E. Wan, Some upper bounds related with domination number, J. Oper. Res. Soc. China, 1 (2013), 217–225. https://doi.org/10.1007/s40305-013-0012-0 doi: 10.1007/s40305-013-0012-0
|
Figures(9)
Jian Yang, Yuefen Chen, Zhiqiang Li. Some sufficient conditions for a tree to have its weak Roman domination number be equal to its domination number plus 1[J]. AIMS Mathematics, 2023, 8(8): 17702-17718. doi: 10.3934/math.2023904
DownLoad: