Dynamic monopolies for interval graphs with bounded thresholds
classification
💻 cs.DM
math.CO
keywords
dynamicgraphsthresholdboundedfunctionsintervalmonopolyvertex
read the original abstract
For a graph $G$ and an integer-valued threshold function $\tau$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $\tau(u)$ neighbors in it eventually yields the vertex set of $G$. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.