Remarks on Dynamic Monopolies with Given Average Thresholds

Carmen C. Centeno; Dieter Rautenbach

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 1, page 133-140
  • ISSN: 2083-5892

Abstract

top
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].

How to cite

top

Carmen C. Centeno, and Dieter Rautenbach. "Remarks on Dynamic Monopolies with Given Average Thresholds." Discussiones Mathematicae Graph Theory 35.1 (2015): 133-140. <http://eudml.org/doc/271228>.

@article{CarmenC2015,
abstract = {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].},
author = {Carmen C. Centeno, Dieter Rautenbach},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dynamic monopoly; degenerate set; vertex cover; independent set},
language = {eng},
number = {1},
pages = {133-140},
title = {Remarks on Dynamic Monopolies with Given Average Thresholds},
url = {http://eudml.org/doc/271228},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Carmen C. Centeno
AU - Dieter Rautenbach
TI - Remarks on Dynamic Monopolies with Given Average Thresholds
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 133
EP - 140
AB - 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].
LA - eng
KW - dynamic monopoly; degenerate set; vertex cover; independent set
UR - http://eudml.org/doc/271228
ER -

References

top
  1. [1] N. Alon, J. Kahn and P.D. Seymour, Large induced degenerate subgraphs, Graphs Combin. 3 (1987) 203-211. doi:10.1007/BF01788542[Crossref] Zbl0624.05039
  2. [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[Crossref] Zbl0986.05060
  3. [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[Crossref] Zbl1254.05135
  4. [4] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197. doi:10.1017/S030500410002168X[Crossref] 
  5. [5] Y. Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979. 
  6. [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[WoS][Crossref] Zbl1246.91115
  7. [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. [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 [WoS][Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.