Contagious sets in a degree-proportional bootstrap percolation process
Contagious sets in a degree-proportional bootstrap percolation process
复制标题
与程度成比例的引导渗透过程中的传染集
DOI：
10.1002/rsa.20818
复制
发表时间：
2018
影响因子：
1
通讯作者：
Garbe F
中科院分区：
文献类型：
--
作者：
Garbe F
我们研究了如下的自举渗流过程：给定一个连通图G，一个常数ρ∈ [0，1]和一个初始的感染顶点集A ∈ V（G），在每一步中，如果至少有ρ-比例的相邻顶点已经被感染，则顶点v成为感染的（一旦被感染，顶点将永远被感染）。我们的重点是研究传染的最小初始集的大小h ρ（G），这意味着这个过程会导致G的每个顶点的传染。我们的主要结果表明，每个连通图Gonnvertices hashρ（G）< 2ρnorhρ（G）= 1（注意，由于这种情况，允许后一种可能性是必要的，因为每个传染集的大小至少为1）。这是这种形式的最佳可能界，并且改进了Chang和Lyuu以及Gentner和Rautenbach的先前结果。我们还为围长至少为5且ρ足够小的图提供了一个更强的界，这是渐近最佳可能的。
We study the following bootstrap percolation process: given a connected graphG, a constantρ∈ [0,1] and an initial setA⊆V(G) ofinfectedvertices, at each step a vertexvbecomes infected if at least aρ‐proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the sizehρ(G) of a smallest initial set which iscontagious, meaning that this process results in the infection of every vertex ofG. Our main result states that every connected graphGonnvertices hashρ(G) < 2ρnorhρ(G) = 1 (note that allowing the latter possibility is necessary because of the case , as every contagious set has size at least one). This is the best‐possible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently smallρ, which is asymptotically best‐possible.