Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes
the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-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 $iin {0, ldots, k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ldots cup D_i$. Denote the size of smallest $tau$-dynamic monopoly by $dyn_{tau}(G)$ and the average of thresholds in $tau$ by $overline{tau}$. We show that the values of $dyn_{tau}(G)$ over all assignments $tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{tau}(G)$ taken over all threshold assignments $tau$ with $overline{tau}leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
