






















Let $G$ be a graph and $τ$ be an assignment of nonnegative integer thresholds to the vertices of $G$. Denote the average of thresholds in $τ$ by $\barτ$. A subset of vertices $D$ is said to be a $τ$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$ and for any $i\in \{0, \ldots, k-1\}$, each vertex $v$ in $D_{i+1}$ has at least $τ(v)$ neighbors in $D_0\cup \ldots \cup D_i$. Denote the size of smallest $τ$-dynamic monopoly by $dyn_τ(G)$. Also a subset of vertices $M$ is said to be a $τ$-static monopoly (or simply $τ$-monopoly) if any vertex $v\in V(G)\setminus M$ has at least $τ(v)$ neighbors in $M$. Denote the size of smallest $τ$-monopoly by $mon_τ(G)$. For a given positive number $t$, denote by $Sdyn_t(G)$ (resp. $Smon_t(G)$), the minimum $dyn_τ(G)$ (resp. $mon_τ(G)$) among all threshold assignments $τ$ with $\overlineτ\geq t$. In this paper we consider the concept of partial vertex cover as follows. Let $G=(V, E)$ be a graph and $t$ be any positive integer. A subset $S\subseteq 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)$. Let $ρ$, $0<ρ<1$ be any fixed number and $G$ be a given bipartite graph with $m$ edges. We first prove that to determine the smallest cardinality of a set $S\subseteq V(G)$ such that $S$ covers at least $ρm$ edges of $G$, is an NP-hard problem. Then we prove that for any constant $t$, $Sdyn_{t}(G)=Pβ_{nt-m}(G)$ and $Smon_t(G)=Pβ_{nt/2}(G)$, where $n$ and $m$ are the order and size of $G$, respectively.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。