Campus Units

Mathematics

Document Type

Article

Publication Version

Published Version

Publication Date

9-26-2017

Journal or Book Title

Discrete Mathematics & Theoretical Computer Science

Volume

19

Issue

3

First Page

5

DOI

10.23638/DMTCS-19-3-5

Abstract

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.

Comments

This article is published as Vyskočil, Tomáš, Bernard Lidický, and Jan Kynčl. "Irreversible 2-conversion set in graphs of bounded degree." Discrete Mathematics & Theoretical Computer Science 19 (2017): 5. doi: 10.23638/DMTCS-19-3-5.

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Download

Share

COinS