Geodesic
Irreversible 2-conversion set in graphs of bounded degree
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3.

Voir la notice de l'article provenant de la source Episciences

An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such that the irreversible $k$-threshold process starting with $S$ black eventually changes all vertices of $G$ to black. We show that deciding the existence of an irreversible 2-conversion set of a given size is NP-complete, even for graphs of maximum degree 4, which answers a question of Dreyer and Roberts. Conversely, we show that for graphs of maximum degree 3, the minimum size of an irreversible 2-conversion set can be computed in polynomial time. Moreover, we find an optimal irreversible 3-conversion set for the toroidal grid, simplifying constructions of Pike and Zou. 
@article{DMTCS_2017_19_3_a5,
     author = {Kyn\v{c}l, Jan and Lidick\'y, Bernard and Vysko\v{c}il, Tom\'a\v{s}},
     title = {Irreversible 2-conversion set in graphs of bounded degree},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-3-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/}
}
TY  - JOUR
AU  - Kynčl, Jan
AU  - Lidický, Bernard
AU  - Vyskočil, Tomáš
TI  - Irreversible 2-conversion set in graphs of bounded degree
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/
DO  - 10.23638/DMTCS-19-3-5
LA  - en
ID  - DMTCS_2017_19_3_a5
ER  - 
%0 Journal Article
%A Kynčl, Jan
%A Lidický, Bernard
%A Vyskočil, Tomáš
%T Irreversible 2-conversion set in graphs of bounded degree
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/
%R 10.23638/DMTCS-19-3-5
%G en
%F DMTCS_2017_19_3_a5
Kynčl, Jan; Lidický, Bernard; Vyskočil, Tomáš. Irreversible 2-conversion set in graphs of bounded degree. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi : 10.23638/DMTCS-19-3-5. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/

Cité par Sources :