Irreversible 2-conversion set in graphs of bounded degree

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10366182" target="_blank" >RIV/00216208:11320/17:10366182 - isvavai.cz</a>

Výsledek na webu

<a href="https://dmtcs.episciences.org/3952" target="_blank" >https://dmtcs.episciences.org/3952</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Irreversible 2-conversion set in graphs of bounded degree

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Irreversible 2-conversion set in graphs of bounded degree

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

—

Svazek periodika

19

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

18

Strana od-do

—

Kód UT WoS článku

000423286200003

EID výsledku v databázi Scopus

2-s2.0-85033566252