×

Remarks on dynamic monopolies with given average thresholds. (English) Zbl 1307.05172

Summary: 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 K. Khoshkhah et al. [Discrete Optim. 9, No. 2, 77–83 (2012; Zbl 1246.91115)] and M. Zaker [Discrete Appl. Math. 161, No. 16–17, 2716–2723 (2013; Zbl 1285.05131)].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, J. Kahn and P.D. Seymour, Large induced degenerate subgraphs, Graphs Combin. 3 (1987) 203-211. doi:10.1007/BF01788542; · Zbl 0624.05039
[2] N. Alon, D. Mubayi and R. Thomas, Large induced forests in sparse graphs, J. Graph Theory 38 (2001) 113-123. doi:10.1002/jgt.1028; · Zbl 0986.05060
[3] P. Borowiecki, F. G¨oring, J. Harant and D. Rautenbach, The potential of greed for independence, J. Graph Theory 71 (2012) 245-259. doi:10.1002/jgt.20644; · Zbl 1254.05135
[4] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197. doi:10.1017/S030500410002168X; · Zbl 0027.26403
[5] Y. Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979.;
[6] K. Khoshkhah, H. Soltani and M. Zaker, On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optimization 9 (2012) 77-83. doi:10.1016/j.disopt.2012.02.001; · Zbl 1246.91115
[7] V.K. Wei, A lower bound on the stability number of a simple graph, Technical Memorandum, TM 81-11217-9, Bell Laboratories, 1981.;
[8] M. Zaker, Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math. 161 (2013) 2716-2723. doi:10.1016/j.dam.2013.04.012; · Zbl 1285.05131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.