Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

A graph GG is said to be kk-degenerate if any subgraph of GG contains a vertex of degree at most kk. The degeneracy of graphs has many applications and was widely studied in graph theory. We first generalize kk-degeneracy by introducing κκ-degeneracy of graphs, where κκ is any non-negative function on the vertex set of the graph. We present a polynomial time algorithm to determine whether a graph is κκ-degenerate. Let τ:V(G)→Zτ:V(G)→Z be an assignment of thresholds to the vertices of GG. A subset of vertices DD is said to be a ττ-dynamic monopoly of GG, if the vertices of GG can be partitioned into subsets D0,D1,…,DkD0,D1,…,Dk such that D0=DD0=D and for any i∈{0,…,k−1}i∈{0,…,k−1}, each vertex vv in Di+1Di+1 has at least τ(v)τ(v) neighbors in D0∪⋯∪DiD0∪⋯∪Di. The concept of dynamic monopolies is used for the formulation and analysis of spread of influence such as disease or opinion in social networks and is the subject of active research in recent years. We obtain a relationship between degeneracy and dynamic monopoly of graphs and show that these two concepts are dual of each other. Using this relationship, we introduce and study dynt(G)dynt(G), which is the smallest cardinality of any ττ-dynamic monopoly among all threshold assignments ττ with average threshold τ̄=t. We give an explicit formula for dynt(G)dynt(G), and obtain some lower and upper bounds for it. We show that dynt(G)dynt(G) is NPNP-complete but for complete multipartite graphs and some other classes of graphs it can be solved by polynomial time algorithms. For the regular graphs, dynt(G)dynt(G) can be approximated within a ratio of nearly 2. Finally we consider the problem of determining the maximum size of κκ-degenerate (or kk-degenerate) induced subgraphs in any graph and obtain some upper and lower bounds for the maximum size of such subgraphs.