Charles Explorer logo
🇨🇿

Irreversible 2-conversion set in graphs of bounded degree

Publikace na Matematicko-fyzikální fakulta |
2017

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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 the vertices of 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.