On f-Reversible Processes on Graphs

Given a graph G and a function f:V(G)→N we study the iterative process on G such that, given an initial vertex labelling c0:V(G)→{0,1}, each vertex v changes its label if and only if at least f(v) of its neighbors have the different label. It is known that these processes reach periodic behavior after a phase called transient. We give a tight upper bound for transient length and we show that the period is at most two, for all c0. We also study the problem of finding the minimum number rf(G) of vertices with initial label 1, such that all vertices reach label 1. Given a constant k≥1, we show that is NP-complete to determine if rf(G)≤k, even if G is a bipartite graph with Δ(G)≤3 and f:V(G)→{1,2,3}. We also prove that this problem is NP-complete for planar cubic graphs and f:V(G)→{3}, through relationship between rf(G) and the size of a minimum vertex cover of G, in the case in which f(v)=d(v), for all vertex v.