Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

DOI10.1016/J.DAM.2013.04.012MaRDI QIDQ2444564zbMATH OpenOpenAlexFDO

Authors Manouchehr Zaker

Publication date 10 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.2856

zbMATH Keywords

degeneracyspread of influenceirreversible dynamic monopolyirreversible \(k\)-threshold process

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07)

Abstract: A graph $G$ is said to be a $k$-degenerate graph if any subgraph of $G$ contains a vertex of degree at most $k$. Let $kappa$ be any non-negative function on the vertex set of $G$. We first define a $kappa$-degenerate graph. Next we give an efficient algorithm to determine whether a graph is $kappa$-degenerate. We revisit the concept of dynamic monopolies in graphs. The latter notion is used in formulation and analysis of spread of influence such as disease or opinion in social networks. We consider dynamic monopolies with (not necessarily positive) but integral threshold assignments. We obtain a sufficient and necessary relationship between dynamic monopolies and generalized degeneracy. As applications of the previous results we consider the problem of determining the maximum size of $kappa$-degenerate (or $k$-degenerate) induced subgraphs in any graph. We obtain some upper and lower bounds for the maximum size of any $kappa$-degenerate induced subgraph in general and regular graphs. All of our bounds are constructive.

Recommendations

• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Remarks on dynamic monopolies with given average thresholds
• On dynamic monopolies of graphs with general thresholds
• On dynamic monopolies of graphs with probabilistic thresholds

Cites work

• scientific article; zbMATH DE number 3480616 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Bootstrap percolation on the hypercube
• Combinatorial model and bounds for target set selection
• Dynamic monopolies with randomized starting configuration
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Graph theory
• Induced Forests in Regular Graphs with Large Girth
• Irreversible \(k\)-threshold and majority conversion processes on complete multipartite graphs and graph products
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Large induced degenerate subgraphs
• Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
• Node-and edge-deletion NP-complete problems
• On dynamic monopolies of graphs with general thresholds
• On dynamic monopolies of graphs: the average and strict majority thresholds
• On the approximability of influence in social networks
• On time versus size for monotone dynamic monopolies in regular topologies

Cited in

(13)

• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• \(H\)-sequences and 2-step coreness in graphs
• On subgraphs of bounded degeneracy in hypergraphs
• On dynamic monopolies of graphs with probabilistic thresholds
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Remarks on dynamic monopolies with given average thresholds
• Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Integer programming approach to static monopolies in graphs

This page was built for publication: Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444564)