pith. sign in

arxiv: 1802.03754 · v1 · pith:2EOJ7O4Cnew · submitted 2018-02-11 · 🧮 math.CO

Partial immunization of trees

classification 🧮 math.CO
keywords dynamicverticesmonopolyproblemthresholdtreesvertexadding
0
0 comments X
read the original abstract

For a graph $G$ and an integer-valued 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 study the problem of maximizing the minimum order of a dynamic monopoly by increasing the threshold values of individual vertices subject to vertex-dependent lower and upper bounds, and fixing the total increase. We solve this problem efficiently for trees, which extends a result of Khoshkhah and Zaker (On the largest dynamic monopolies of graphs with a given average threshold, Canadian Mathematical Bulletin 58 (2015) 306-316).

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.