Weak \(\{2\}\)-domination number of Cartesian products of cycles (Q1698059): Difference between revisions

In this paper, the authors introduce a discharging approach and provided a short proof for computing the lower bound of the weak\(\left\{2\right\}\)-domination number of \(C_n \times C_5\). They obtain the weak\(\left\{2\right\}\)-domination number of \(C_n \times C_3\) and \(C_n \times C_4\). They determine the weak\(\left\{2\right\}\)-domination number of some special classes of graphs. The problems on domination and Roman domination of graphs have been investigated widely by \textit{C. Bujtás} and \textit{S. Klavžar} [Graphs Comb. 32, No. 2, 511--519 (2016; Zbl 1339.05280)], \textit{W. Goddard} and \textit{M. A. Henning} [J. Graph Theory 40, No. 1, 1--25 (2002; Zbl 0997.05072)], \textit{T. W. Haynes} (ed.) et al. [Domination in graphs. Advanced topics. New York, NY: Marcel Dekker (1998; Zbl 0883.00011)], \textit{Z. Li} et al. [Discrete Appl. Math. 198, 164--169 (2016; Zbl 1327.05263)], \textit{L. R. Matheson} and \textit{R. E. Tarjan} [Eur. J. Comb. 17, No. 6, 565--568 (1996; Zbl 0862.05032)] and \textit{E. W. Chambers} et al. [SIAM J. Discrete Math. 23, No. 3, 1575--1586 (2009; Zbl 1207.05135)], \textit{E. J. Cockayne} et al. [Discrete Math. 278, No. 1--3, 11--22 (2004; Zbl 1036.05034)], \textit{O. Favaron} et al. [Discrete Math. 309, No. 10, 3447--3451 (2009; Zbl 1191.05071)], \textit{M. Liedloff} et al. [Discrete Appl. Math. 156, No. 18, 3400--3415 (2008; Zbl 1180.05113)]. The concept of 2-rainbow domination was introduced by \textit{B. Brešar} et al. [Taiwanese J. Math. 12, No. 1, 213--225 (2008; Zbl 1163.05046)] and has been widely studied by \textit{B. Brešar} and \textit{T. K. Šumenjak} [Discrete Appl. Math. 155, No. 17, 2394--2400 (2007; Zbl 1126.05091)], \textit{Z. Shao} et al. [Inf. Sci. 254, 225--234 (2014; Zbl 1321.05190)], \textit{Z. Stȩpień} and \textit{M. Zwierzchowski} [J. Comb. Optim. 28, No. 4, 748--755 (2014; Zbl 1307.90191)], \textit{Z. Stȩpień} et al. [J. Comb. Optim. 30, No. 3, 668--674 (2015; Zbl 1321.05191)], \textit{Y.-L. Wang} and \textit{K.-H. Wu} [Discrete Appl. Math. 161, No. 13--14, 2178--2188 (2013; Zbl 1286.05127)], \textit{Y. Wu} and \textit{N. J. Rad} [Graphs Comb. 29, No. 4, 1125--1133 (2013; Zbl 1268.05154)]. \textit{B. Brešar} et al. [loc. cit] introduced a monochromatic version of 2-rainbow domination, called weak \(\{2\}\)-dominating functions. The weak \(\{2\}\)-domination can be thought of as a variant of Roman domination. \textit{M. Chellali} et al. [Discrete Appl. Math. 204, 22--28 (2016; Zbl 1333.05217)] independently proposed the concept of weak \(\{2\}\)-domination and called it Roman \(\{2\}\)-domination. The decision problem of weak \(\{2\}\)-domination is NP-complete, even for bipartite graphs or chordal graphs [M. Chellali et al., loc. cit., B. Brešar and T. K. Šumenjak, loc. cit.]. Here, the authors compute the weak \(\{2\}\)-domination numbers of some special classes of graphs. The authors note a lower bound on weak \(\{2\}\)-domination numbers of graphs due to M. Chellali et al. [loc. cit.], which they use for their investigations. Lemma 1: [M. Chellali et al., loc. cit.] If G is a connected graph, then \[ \gamma_{w2}(G) \geq \frac{2\left|V(G)\right|}{\Delta(G)+2} \] . Using Lemma 1, the authors produce a short proof for the lower bound of \(\gamma_{w2}(C_{n} \times C_{5})\). Then, the authors compute the weak \(\{2\}\)-domination number of \(\gamma_{w2}(C_{n} \times C_{3})\). Also they compute the weak \(\{2\}\)-domination number of \(\gamma_{w2}(C_{n} \times C_{5})\). Finally, they have compute the weak \(\{2\}\)-domination number of Cartesian products of cycles. It is an excellent work in the area of domination in graphs. We are able to experience mathematical rigor throughout the paper. For researchers, it will be a good experience to read this paper.