Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
复制标题
周长至少为五的连通图中的度比例阈值和树的动态垄断
DOI：
10.1016/j.tcs.2016.12.028
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
M. Gentner;D. Rautenbach
设G是一个图，ρ∈[0，1].对于G的一个顶点集合D，设集合H ρ（D）是从集合D开始的，如果在当前集合中有至少的邻居，则迭代地将更多的顶点u添加到当前集合中。如果H ρ（D）包含G的所有顶点，则D被称为不可逆动态垄断或与阈值函数u相关的完美目标集合。设h ρ（G）是这种不可逆动态垄断的最小基数.对于最大度至少为1 ρ的连通图G，Chang证明了h ρ（G）≤ 5.83 ρ n（G），Chang和Lyuu改进了h ρ（G）≤ 4.92 ρ n（G）.本文证明了：对于任意的ρ> 0，存在ρ（ρ）∈（0，1）使得对（0，ρ（G））中的任意ρ，h ρ（G）≤（2+ ρ）ρ n（G），且对任意的连通图G，最大度至少为1 ρ，围长至少为5.进一步证明了对于（0，1]中的任意ρ，以及任意阶至少为1 ρ的树T，h ρ（T）≤ ρ n（T）.
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 ρ.
登录
查看更多内容
不可逆发电机的包含层次结构
影响因子：
1.1
作者：
S. Brunetti;E. Lodi;Walter Quattrociocchi
通讯作者：
Walter Quattrociocchi
DOI：
--
发表时间：
2007
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Joseph Lauer;N. Wormald
通讯作者：
N. Wormald
对基于多数的网络系统中的故障传播进行建模：三角网格中的动态垄断
影响因子：
1.1
作者：
Sarah Spence Adams;Paul Booth;Denise Sakai Troxell;Harold Jaffe
通讯作者：
Harold Jaffe
大周长正则图中的局部密集独立集 - 新方法的示例
DOI：
--
发表时间：
2008
期刊：
Bonn Workshop of Combinatorial Optimization
影响因子：
--
作者：
L. Margulis
通讯作者：
L. Margulis
不可逆的 k 阈值过程：疾病和观点传播的图论阈值模型
DOI：
10.1016/j.dam.2008.09.012
发表时间：
2009
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Paul A. Dreyer;F. Roberts
通讯作者：
F. Roberts