Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optimization 9 (2012) 77-83] and Zaker [Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math. 161 (2013) 2716-2723].
José D. Alvarado, Simone Dantas and Dieter Rautenbach
For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer k, the recognition of the connected K4-free graphs G with yR(G) − yr2(G) = k is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs G such that yr2(H) = yR(H) for every induced subgraph H of G, and collect several properties of the graphs G with R(G) = 3/2yr2(G).