Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871109 | Discrete Applied Mathematics | 2018 | 17 Pages |
Abstract
An f-reversible process on a graph G=(V,E) is a graph dynamical system on V(G) defined as follows. Given a function f:V(G)âN and an initial vertex labeling c0:V(G)â{0,1}, every vertex v changes its label if and only if at least f(v) of its neighbors have the opposite state, synchronously in discrete-time. For such processes, we present a new nondecreasing time function similar to the monotonically decreasing energy functions used to study threshold networks, which leads to a periodic behavior after a transient phase. Using this new function, we provide a tight upper bound on the transient length of f-reversible processes. Furthermore, we prove that it is equal to nâ3 for trees with nâ¥4 vertices and Im(f)={2}. Moreover we present an algorithm that generates all the initial configurations attaining this bound and we prove that the number of such configurations is O(n). We also consider the problem of determining the smallest number rf(G) of vertices with initial label 1 for which all the vertices eventually reach label 1 after the complete evolution of the dynamics, which models consensus problems on networks. We prove that it is NP-hard to compute rf(G) even for bipartite graphs with Î(G)â¤3 and Im(f)={1,2,3}. Finally, we prove that β(G)â¤rf(G)â¤Î²(G)+1, when f(v)=d(v) for all vâV(G), where β(G) is the size of a minimum vertex cover of G.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carlos V.G.C. Lima, Leonardo I.L. Oliveira, Valmir C. Barbosa, Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter,