Contagious sets in a degree-proportional bootstrap percolation process
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00496182" target="_blank" >RIV/67985840:_____/18:00496182 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1002/rsa.20818" target="_blank" >http://dx.doi.org/10.1002/rsa.20818</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/rsa.20818" target="_blank" >10.1002/rsa.20818</a>
Alternative languages
Result language
angličtina
Original language name
Contagious sets in a degree-proportional bootstrap percolation process
Original language description
We study the following bootstrap percolation process: given a connected graph G, a constant ρ ∈ [0,1] and an initial set A⊆V(G) of infected vertices, at each step a vertex v becomes infected if at least a ρ-proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the size hρ(G) of a smallest initial set which is contagious, meaning that this process results in the infection of every vertex of G. Our main result states that every connected graph G on n vertices has hρ(G) < 2ρn or hρ(G) = 1 (note that allowing the latter possibility is necessary because of the case (Formula presented.), 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Random Structures and Algorithms
ISSN
1042-9832
e-ISSN
—
Volume of the periodical
53
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
14
Pages from-to
638-651
UT code for WoS article
000449519300005
EID of the result in the Scopus database
2-s2.0-85055686585