Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies

Abstract

Let G be a graph and r be an assignment of nonnegative integer thresholds to the vertices of G. Denote the average of thresholds in t by f. A subset of vertices D is said to be a r-dynamic monopoly, if V(G) can be partitioned into subsets D₀, Di,..., D∗ such that D₀ = D and for any i ϵ {0,...,fc - 1}, each vertex v in Di+1 has at least t(v) neighbors in D₀ U ... U Di. Denote the size of smallest r-dynamic monopoly by dynr{G). Also a subset of vertices M is said to be a r-static monopoly (or simply r-monopoly) if any vertex v ϵ V(G) \ M has at least r(v) neighbors in M. Denote the size of smallest r-monopoly by monr(G). For a given positive number t, denote by Sdynt[G) (resp. 5mont(G)), the minimum dynr(G) (resp. monT(G)) among all threshold assignments r with r > t. Let G = (V,G) be a graph and t be any positive integer. A subset S ⊆ V is said to be a t-partial vertex cover of G} if S covers at least t edges of G. Denote the smallest size of a t-partial vertex cover of G by Pβt{G). In this paper we first prove an NP-completeness result concerning Pβt{G). Then we obtain two expressions for Sdynt{G) and Smont(G) in terms of partial vertex covers. It follows that to determine Sdynkϵ{G)(G) (1 < k < 2) and Smonk€{G)(G) (0 < k < 2) is NP-hard for various classes of graphs, but polynomial-Time for trees, where 6(G) is the edge density of G and k any fixed number. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.