Let $ G $ be a nontrivial graph and $ k\geq 1 $ an integer. Given a vector of nonnegative integers $ w = (w_0, \ldots, w_k) $, a function $ f: V(G)\rightarrow \{0, \ldots, k\} $ is a $ w $-dominating function on $ G $ if $ f(N(v))\geq w_i $ for every $ v\in V(G) $ such that $ f(v) = i $. The $ w $-domination number of $ G $, denoted by $ \gamma_{w}(G) $, is the minimum weight $ \omega(f) = \sum_{v\in V(G)}f(v) $ among all $ w $-dominating functions on $ G $. In particular, the $ \{2\} $-domination number of a graph $ G $ is defined as $ \gamma_{\{2\}}(G) = \gamma_{(2, 1, 0)}(G) $. In this paper we continue with the study of the $ \{2\} $-domination number of graphs. In particular, we obtain new tight bounds on this parameter and provide closed formulas for some specific families of graphs.
Citation: Abel Cabrera-Martínez, Andrea Conchado Peiró. On the $ \{2\} $-domination number of graphs[J]. AIMS Mathematics, 2022, 7(6): 10731-10743. doi: 10.3934/math.2022599
Let $ G $ be a nontrivial graph and $ k\geq 1 $ an integer. Given a vector of nonnegative integers $ w = (w_0, \ldots, w_k) $, a function $ f: V(G)\rightarrow \{0, \ldots, k\} $ is a $ w $-dominating function on $ G $ if $ f(N(v))\geq w_i $ for every $ v\in V(G) $ such that $ f(v) = i $. The $ w $-domination number of $ G $, denoted by $ \gamma_{w}(G) $, is the minimum weight $ \omega(f) = \sum_{v\in V(G)}f(v) $ among all $ w $-dominating functions on $ G $. In particular, the $ \{2\} $-domination number of a graph $ G $ is defined as $ \gamma_{\{2\}}(G) = \gamma_{(2, 1, 0)}(G) $. In this paper we continue with the study of the $ \{2\} $-domination number of graphs. In particular, we obtain new tight bounds on this parameter and provide closed formulas for some specific families of graphs.
| [1] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998. |
| [2] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs: Advanced Topics, Chapman & Hall/CRC Pure and Applied Mathematics, Taylor & Francis, 1998. |
| [3] | T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Topics in Domination in Graphs, Springer International Publishing, Cham, 2020. https://doi.org/10.1007/978-3-030-51117-3 |
| [4] |
A. Cabrera Martínez, A. Estrada-Moreno, J. A. Rodríguez-Velázquez, From Italian domination in lexicographic product graphs to $w$-domination in graphs, ARS Math. Contemp., 22 (2022), P1.04. https://doi.org/10.26493/1855-3974.2318.fb9 doi: 10.26493/1855-3974.2318.fb9
|
| [5] | M. A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, 2013. https://doi.org/10.1007/978-1-4614-6525-6 |
| [6] |
M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math., 309 (2009), 32–63. https://doi.org/10.1016/j.disc.2007.12.044 doi: 10.1016/j.disc.2007.12.044
|
| [7] |
F. Bonomo, B. Brešar, L. N. Grippo, M. Milanič, M. D. Safe, Domination parameters with number 2: interrelations and algorithmic consequences, Discrete Appl. Math., 235 (2018), 23–50. https://doi.org/10.1016/j.dam.2017.08.017 doi: 10.1016/j.dam.2017.08.017
|
| [8] |
A. Cabrera Martínez, J. A. Rodríguez-Velázquez, A note on double domination in graphs, Discrete Appl. Math., 300 (2021), 107–111. https://doi.org/10.1016/j.dam.2021.05.011 doi: 10.1016/j.dam.2021.05.011
|
| [9] | A. Hansberg, L. Volkmann, Multiple domination, In: Topics in domination in graphs, vol. 64 of Dev. Math., Springer, Cham (2020), 151–203. https://doi.org/10.1007/978-3-030-51117-3_6 |
| [10] | F. Harary, T. W. Haynes, Double domination in graphs, Ars Combin., 55 (2000), 201–213. |
| [11] |
M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math., 204 (2016), 22–28. https://doi.org/10.1016/j.dam.2015.11.013 doi: 10.1016/j.dam.2015.11.013
|
| [12] | M. A. Henning, W. F. Klostermeyer, Italian domination in trees, Discrete Appl. Math., 217 (2017), 557–564. https://doi.org/10.1016/j.dam.2016.09.035 |
| [13] | W. F. Klostermeyer, G. MacGillivray, Roman, Italian, and $2$ domination, J. Combin. Math. Combin. Comput., 108 (2019), 125–146. |
| [14] |
S. Cabrera García, A. Cabrera Martínez, F. A. Hernández Mira, I. G. Yero, Total Roman $\{2\}$-domination in graphs, Quaest. Math., 44 (2021), 411–434. https://doi.org/10.2989/16073606.2019.1695230 doi: 10.2989/16073606.2019.1695230
|
| [15] | H. Abdollahzadeh Ahangar M. Chellali, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro, Total Roman $\{2\}$-dominating functions in graphs, Discuss. Math. Graph Theory, (2020), In press. https://doi.org/10.7151/dmgt.2316 |
| [16] |
A. Cabrera Martínez, S. Cabrera García, J. A. Rodríguez-Velázquez, Double domination in lexicographic product graphs, Discrete Appl. Math., 284 (2020), 290–300. https://doi.org/10.1016/j.dam.2020.03.045 doi: 10.1016/j.dam.2020.03.045
|
| [17] |
B. Brešar, M. A. Henning, S. Klavžar, On integer domination in graphs and Vizing-like problems, Taiwanese J. Math., 10 (2006), 1317–1328. https://doi.org/10.11650/twjm/1500557305 doi: 10.11650/twjm/1500557305
|
| [18] | G. S. Domke, S. T. Hedetniemi, R. C. Laskar, G. H. Fricke, Relationships between integer and fractional parameters of graphs, In: Graph theory, combinatorics, and applications: proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University, volume 2, John Wiley & Sons Inc. (1991), 371–387. |
| [19] | X. Hou, Y. Lu, On the $\{k\}$-domination number of cartesian products of graphs, Discrete Math., 309 (2009), 3413–3419. |
| [20] |
C. M. Lee, M. S. Chang, Variations of $Y$-dominating functions on graphs, Discrete Math., 308 (2008), 4185–4204. https://doi.org/10.1016/j.disc.2007.08.080 doi: 10.1016/j.disc.2007.08.080
|
| [21] |
A. Cabrera Martínez, I. G. Yero, Constructive characterizations concerning weak Roman domination in trees, Discrete Appl. Math., 284 (2020), 384–390. https://doi.org/10.1016/j.dam.2020.03.058 doi: 10.1016/j.dam.2020.03.058
|
| [22] |
A. Cabrera Martínez, D. Kuziak, I. G. Yero. A constructive characterization of vertex cover Roman trees, Discuss. Math. Graph Theory, 41 (2021), 267–283. https://doi.org/10.7151/dmgt.2179 doi: 10.7151/dmgt.2179
|
| [23] |
W. J. Desormeaux, T. W. Haynes, M. A. Henning, Improved bounds on the domination number of a tree, Discrete Appl. Math., 177 (2014), 88–94. https://doi.org/10.1016/j.dam.2014.05.037 doi: 10.1016/j.dam.2014.05.037
|
| [24] |
G. S. Domke, J. H. Hattingh, M. A. Henning, L. R. Markus, Restrained domination in trees, Discrete Math., 211 (2000), 1–9. https://doi.org/10.1016/S0012-365X(99)00036-9 doi: 10.1016/S0012-365X(99)00036-9
|
| [25] | M. Chellali, T. W. Haynes, A note on the total domination of a tree, J. Comb. Math. Comb. Comput., 58 (2006), 189–193. |
| [26] | M. Lemanska, Lower bound on the domination number of a tree. Discuss. Math. Graph Theory, 24 (2004), 165–169. https://doi.org/10.7151/dmgt.1222 |
| [27] | E. Shan, L. Kang, M. A. Henning, A characterization of trees with equal total domination and paired-domination numbers, Australas. J. Comb., 30 (2004), 31–39. |
| [28] |
A. Cabrera Martínez, A. Estrada-Moreno, J. A. Rodríguez-Velázquez, From (secure) w-domination in graphs to protection of lexicographic product graphs, Bull. Malays. Math. Sci. Soc., 44 (2021), 3747–3765. https://doi.org/10.1007/s40840-021-01141-8 doi: 10.1007/s40840-021-01141-8
|
| [29] |
A. Cabrera Martínez, A. Estrada-Moreno, J. A. Rodríguez-Velázquez, Secure w-domination in graphs, Symmetry, 12 (2020), 1948. https://doi.org/10.3390/sym12121948 doi: 10.3390/sym12121948
|
Figures(2)
Abel Cabrera-Martínez, Andrea Conchado Peiró. On the $ \{2\} $-domination number of graphs[J]. AIMS Mathematics, 2022, 7(6): 10731-10743. doi: 10.3934/math.2022599
DownLoad: