Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

详细信息    查看全文

• 作者：Manouchehr Zaker
• 关键词：Degeneracy ; Irreversible dynamic monopoly ; Spread of influence ; Irreversible kk-threshold process
• 刊名：Discrete Applied Mathematics
• 出版年：2013
• 出版时间：November, 2013
• 年：2013
• 卷：161
• 期：16-17
• 页码：2716-2723
• 全文大小：396 K

文摘

A graph is said to be -degenerate if any subgraph of contains a vertex of degree at most . The degeneracy of graphs has many applications and was widely studied in graph theory. We first generalize -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 be an assignment of thresholds to the vertices of . A subset of vertices is said to be a -dynamic monopoly of , if the vertices of can be partitioned into subsets such that and for any , each vertex in has at least neighbors in . 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 , which is the smallest cardinality of any -dynamic monopoly among all threshold assignments with average threshold . We give an explicit formula for , and obtain some lower and upper bounds for it. We show that is -complete but for complete multipartite graphs and some other classes of graphs it can be solved by polynomial time algorithms. For the regular graphs, can be approximated within a ratio of nearly 2. Finally we consider the problem of determining the maximum size of -degenerate (or -degenerate) induced subgraphs in any graph and obtain some upper and lower bounds for the maximum size of such subgraphs.