2012/12/15 by Kaveh Khoshkhah, Khoshkhah, Kaveh, Hossein Soltani +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Engineering · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #ICT Impact and Policies #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1212.3682
arxiv created 2012/12/15 · openalex publication_date 2012/12/15 · arxiv updated 2012/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a directed graph such that the in-degree of any vertex G is at least one. Let also \mathcalτ: V(G)→ ℕ be an assignment of thresholds to the vertices of G. A subset M of vertices of G is called a dynamic monopoly for (G,τ) if the vertex set of G can be partitioned into D0∪... ∪ Dt such that D0=M and for any i≥ 1 and any v∈ Di, the number of edges from D0∪... ∪ Di-1 to v is at least τ(v). One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex v, τ(v)=\lceil (degin(v)+1)/2 \rceil, where degin(v) stands for the in-degree of v. By a strict majority dynamic monopoly of a graph G we mean any dynamic monopoly of G with strict majority threshold assignment for the vertices of G. In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness complexity results concerning the smallest size of dynamic monopolies in directed graphs. Next we show that any directed graph on n vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with n/2 vertices. We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the best known result. The final note of the paper deals with the possibility of the improvement of the latter n/2 bound.