Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees

作者：Gentner Michael; Rautenbach Dieter^*

来源：Theoretical Computer Science, 2017, 667: 93-100.

DOI：10.1016/j.tcs.2016.12.028

• Irreversible dynamic monopoly
• Perfect target set

Let G be a graph, and let p is an element of [0, 1]. For a set D of vertices of G, let the set H-rho(D) arise by starting with the set D, and iteratively adding further vertices u to the current set if they have at least [rho d(G)(u)] neighbors in it. If H-rho(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 proves > [rho d(G)(u)]. Let h(rho)(G) be the minimum cardinality of such an irreversible dynamic monopoly.
For a connected graph G of maximum degree at least 1/rho, Chang showed h(rho)(G) <= 5.83 rho n(G), which was improved by Chang and Lyuu to h(rho)(G) <= 4.92 rho n(G). We show that for every is an element of > 0, there is some rho(is an element of) is an element of (0,1) such that h(rho)(G) <= (2 + is an element of)rho n(G) for every p in (0, rho(is an element of)), and every connected graph G that has maximum degree at least 1/rho and girth at least 5. Furthermore, we show that h(rho)(T) <= rho n(T) for every rho in (0,1], and every tree T that has order at least 1/rho.

• 出版日期2017-3-8