Paper Info
Title
Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees.
Abstract
Let G be a graph, and let ź ź 0 , 1 . For a set D of vertices of G, let the set H ź ( D ) arise by starting with the set D, and iteratively adding further vertices u to the current set if they have at least ź ź d G ( u ) ź neighbors in it. If H ź ( D ) contains all vertices of G, then D is known as an irreversible dynamic monopoly or a perfect target set associated with the threshold function u ź ź ź d G ( u ) ź . Let h ź ( G ) be the minimum cardinality of such an irreversible dynamic monopoly.For a connected graph G of maximum degree at least 1 ź , Chang showed h ź ( G ) ź 5.83 ź n ( G ) , which was improved by Chang and Lyuu to h ź ( G ) ź 4.92 ź n ( G ) . We show that for every ź 0 , there is some ź ( ź ) ź ( 0 , 1 ) such that h ź ( G ) ź ( 2 + ź ) ź n ( G ) for every ź in ( 0 , ź ( ź ) ) , and every connected graph G that has maximum degree at least 1 ź and girth at least 5. Furthermore, we show that h ź ( T ) ź ź n ( T ) for every ź in ( 0 , 1 , and every tree T that has order at least 1 ź .
Year
DOI
Venue
2017
10.1016/j.tcs.2016.12.028
Theor. Comput. Sci.
Keywords
DocType
Volume
Irreversible dynamic monopoly,Perfect target set
Journal
667
Issue
ISSN
Citations 
C
0304-3975
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Michael Gentner1224.46
Dieter Rautenbach2946138.87